Du får förtydliga; är det endast Exchange du söker eller vill du ha 'mailkonton', dvs ej nödvändigt Exchange?
Är det mailkonton du vill fixa så räcker det ju med att fixa ett konto hos ett webbhotell, något av de större kända ex. Loopia, One, FS Data mm. Där får du tillgång till mailtjänst ifrån av IMAP eller POP3, åtkomst ifrån mail via webbläsare. Ang mobilen så tror jag, utan att använt windows mobile, den har en mailklient som stödjer både imap och pop3.
Är det en Exchange-lösning du vill ha så blir det genast mycket mer omständigt. Oftast mindre företag som erbjuder 'exchange-hosting'-paket. Beroende på hur hög tillförlitlighet ni vill ha kontra kostnad så hade jag tittat på någon av de större och etablerade aktörerna på marknaden, gått på en VPS och satt upp allt själv.