RIM has been following this issue for a while. I do not believe it is fixed yet. Basically, the BIS polls a message count of zero and polls a set of old email again, as it did not "remember" the previous UIDs.

If removing/re-integrating does not fix it, you will need to setup a forwarding rule to a blackberry.net email address until the issue is patched on the BIS.