Here is the answer I received from Microsoft:
*************************************
After reviewing your message, I perform an extensible research and find that
the Modified Date only records the delete operation in the Exchange
environment. If the email account is an Internet Email service, the delete
operation in Outlook is the same as the operations of moving messages to
other folders. Thus, there is no specific status for the delete operation.
Without the message status changed, we cannot track the deleted date.
If you are using an Exchange account and the Modified Date cannot be used to
check the delete date of the deleted items, please do not hesitate to let me
know, I will try all my best to resolve the issue.
If you are using an Internet Email account, I am sorry for the inconvenience
that this by-design feature of our products has caused you. I can understand
how frustrating it is when you find that the product does not meet your
needs.
*************************************
I am using Internet Email service, and that explains why I couldn't get the
Modified Date to work correctly.
Debbie
This thread was the first one I found when Deja-Googling for sorting
by the deleted date - the solution of using the modifed date works
fine here, running Outlook 2002 (10.4705.4219) SP-2.