What's the current state of Exchange-as-a-cloud-service? Just randomly Googling, it seems that RackSpace offers Exchange for $10/user. Something like that lets them keep the same look and feel, only a failure of the box in the basement isn't an instant catastrophe.

I suppose if I were building a clean-slate small legal office, I'd put them on Google Apps with a decently fast Internet connection and a consumer-grade router. I'd be tempted to get them a cheap file server as well, something with RAID5, but maybe all they really need is the USB port on that consumer-grade router with a cheap hard drive.