There's a nugget of truth in their concerns which makes them harder to dismiss. Equally, can you say that local storage is more secure, tapes in a "fire-proof" safe, etc? I have reservations about the cloud (Amazon's outage was a wake-up moment for me) but nothing's perfect.

As for Google Mail vs Exchange, my personal opinion is that Gmail is superior in evey way. If you need discovery, you can always shove email through your own gateway (running Postfix) and set it to store all emails it sends and receives. You could also use Postini which I think gives extra facilities like discovery. Might be a bit hacky for some organisations I suppose but I've never found Exchange that elegant or easy to manage.