Users who have been migrated from Exchange 2000 to Exchange 2003 do not have the "empty deleted items" option when they right-click on their deleted items folder. in fact, the deleted items folder looks like a normal folder - it doesn't have the bin image.
I can open these mailboxes remotely and the empty option appears. I can then delete the folders. But the users still cannot delete their items.
There is a mix of clients, but mostly Outlook XP and 2000.
This was posted on http://hdsurvivor.blogspot.com/2006/07/cannot-empty-deleted-items-in-outlook.html
and they recomment an exmerge solution. This is fine, but with 500 users it's something I'd rather avoid.