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.  If the various states that a single order can be in are not based on user, then modify the table to reference that instead.

Then you can join theses states to the orders based on the user and sort on states as desired.  If you need to store the sorting rules by user profile, you can also store that in another table:

    Profile | Status | Priority
    ---------------------------
          1 | 5      | 1
          1 | 4      | 2
          1 | 2      | 3
          2 | 3      | 1
          2 | 2      | 2

And each user is assigned a profile.  You can then join this with the table above and the orders table and add an `ORDER BY` on `priority` to the query.