Same problem here. Worked find for 3.5 years, but started to fail with the "unable to find message" on Friday June 7th. GMail via Nokia messaging works. No change to modest or any installed software, I suspect it is something to do with a gmail change.