In the past I have experienced that you need to restart the BlackBerry server service (dispatcher in 4.0) to get them working again, as the service doesn't properly detect the move between mailbox stores on the same Exchange server.
Sometimes you can do a user "Reload", but I agree with akdumga, most of the time I have to restart the Dispatcher service to get BES to recognize the move. I was hoping SP2 would fix that but it didn't.
I have seen this as well. The only option is to restart BES. RIM does have an open SDR to add the functionality to an updated version of the handheldcleanup utility to detect these moves, but no timeframe when it will be available.