It goes wihtout saying, that you'll need at least 2 servers (preferably 4), to achieve what you describe. This is just an (easy-to-manage) example, where each server holds HUB,CAS and MBX roles:
2 identical physical servers, one in each datacenter.
- Install the Hub Transport Server, Client Access Server and Mailbox Server Roles on each server.
- Create a CAS array to ensure Client Access to mailboxes.
- Create a Database Availability Group, and set up Mailbox Database replicas
- If you have the resources (like 2 extra servers), you might want to consider publishing OWA and other Client Access features through a proxy, preferably a Forefront TMG Server 2010 array. You might wan't to combine the Edge Transport Role and the TMG Server in one, see this link
In this scenario you would need 4 Exchange Server 2010 Standard Server licenses and 25 Std CALs. If you wish to use the Forefront for Exchange security features, I would probably go for Enterprise CAL's (they include Forefront for Exchange + Forefront Endpoint protection for all the clients). Beware that the 2 servers used for the CAS/MBX roles need to be Enterprise or Datacenter Edition servers, in order to set up the Site Resiliency features (requires Failover Clustering and NLB)
That all being said, with 25-50 users, and HA as a high priority, I'd definitely say: Go O365! Unless you have a specific need for a custom setup or any "on-premise" demands, so to say, there's not many reasons not to buy a cloud service instead of hosting it yourself. Then again, depends on your needs and your resources