With IMAP you just gotta sync the device with X number of days. Now, I did not use VersaSmell, so good luck there. However, ChatterEmail does support GMail and is still available, though not for much longer. Is there a setting in your email application to sync X number of days back? If not, after the initial sync life should be good.
The problem you are seeing is that GMail is not a standard mail server. You delete and really not delete. With POP, once you see it, it is deleted from the server UNLESS you can find a setting to LEAVE it on the server. And with GMail's method of handling messages, well your application has to be able to handle it and I do not believe the 650's VersaSmell is able to do that. IMAP syncs your messages so that what you see on the server is what you see on your device is what you see...see what I mean. Another email application that may be worth looking at is Snapper 3.x -
http://snappermail.com/.
Good luck.