OVH do quite a good hosted Exchange solution, they're quite big in Europe and have a fair reputation for what they do. There's even the option for a dedicated server which they manage if you're worried about security
Is it likely that POP and SMTP are not going to be on by default if we go with OVH? (Sorry if that's stupid, I'm under the impression that Exchange uses its own protocol.)