The simple solution here is to create a separate table that 'hangs off' of the order table.  Something along the lines of:

    Order | State | User
    --------------------
      100 | 4     | 128
      100 | 3     | 583
      101 | 2     | 128
      101 | 3     | 583

I've substituted the word 'state' for 'priority' here because it seems to match what you are doing better.  You can see here that the same orders are assigned different states for different users.

Then you can join theses states to the orders based on the user and sort on states as desired.