I've seen a similar issue from time to time when moving an account to a different mail server. The user is able to sync their calendar and contacts but their mail stops synching, and only a few random emails are visible. I do a reset on the user in Traveler. I then remove Verse from the device and re-add it. Mail is then displayed on the device. It appears that there are both server side and device side components to the problem.