More like all users would complain. Don't get me wrong, it sounds like like a good solution, but you would be amazed at the recalcitrance of users asked to do something new or different. Plus, your infrastructure and user workflows have to be able to support such a setup. If a user who travels a lot is utterly dead in the water without his dozen 10GB email archive files, and the VPN is a tiny 1mb/s pipe for the whole globe, the above isn't a particularly viable idea.
Most email clients let you store your archive online. Exchange certainly does - I can search from my phone, which only stores the last week's work email locally.
