If you do Reconcile Now, it should delete them, yes. If you are using Cached Mode in Outlook 2003, be sure to do a Send/Receive to force an update on the Exchange server.
If that does work, but it doesn't work on its own within the 20 minute interval, then you may be experiencing the issue we had. You can do this command from the command-line on a DC to check the displayName value:
ldifde -f users.txt -r "(objectClass=user)" -s DCSERVERNAME
Look for the displayName value for a user in question to verify that it is the same thing that is actually being displayed (either with ADUC or BESMC). This is just one issue that caused problems for us. You can view the MAGT log on the BES and see the mailbox being stopped/started every 12 minutes, reporting that there was a mailbox move detected.
This probably isn't your issue, but just gives you an idea that the issue, if not user impatience, could be something thats not exactly apparent at first or second glance.
In the beginning the Universe was created. This has made a lot of people very angry and is widely regarded as a bad move.