Got it...I didn't even think about that field being called 'icon'.
Using Outlook 2000 SR-3 here, it seems to work with 1 exception which might be what you're referring to.
The Descending sort is:[ul]
[li]Forwarded messages[/li]
[li]Replied messages[/li]
[li]neither forwarded or replied[/li][/ul]
The Ascending sort is:[ul]
[li]neither forwarded or replied[/li]
[li]Replied messages[/li]
[li]Forwarded messages[/li][/ul]
The read/unread status does not appear to be used for sorting, even though their 'icons' are different. This is what I suspect that you're seeing and I don't know any way to change this.