I've got something I've seen before, but I can't find the solution:

I've got a user, whom's inbox is sorted on date, sorted oldest on top, newest below
New mail however arrives in the top of his inbox, above all other (read or unread, doesn't matter) mail.
When he switches to another folder and back again, the new mail is where it should be: at the end of the list.

Anyone know the answer?