Hosted exchange spam filter

Hi all,

A client of mine uses hosted exchange solution for his business with 10 computers and few weeks ago the company that provides the hosted exchange solution asked to switch the MX records because they said that google stops providing postini spam filter and they will start using spam expert spam filter instead.
the MX records were updated last week and people in the client's company are complaining of losing some important incoming emails and also getting more junk than before.
The hosted exchange company said they haven't experienced these kind of problems with the migrated clients, and there isn't another spam solution they can provide.
I asked them to cancel the spam filter for now and try to think about solution I can offer to the client :
1. 3rd party spam like spamfighter (I mean the free version, Just hope it'll work with hosted exchange settings)
2. Migrating them to google apps which to my understanding provides good spam filter compatible with previous postini

What do you think ? Any other solution you can suggest me ?

Thank you