Eh?
If your IT guys can't keep a handful of virtual / dedicated servers online, you don't have an IT department, more a cage full of monkeys.
And you *can't* host entirely in-house, except for maybe a single set of mail servers - that's kinda the point of multiple MX records and redundancy. And if you *can't* manage a couple of virtual / dedicated servers doing email for a domain, then obviously anything "external" (cloud or not) is the way to go. It was called webmail. People who used it for business purposes were kinda looked down on unless it was an in-house webmail.
The point is that if you want to keep your Data Protection Registration, you're almost certainly better off doing it yourself. Seriously, it takes about 10 minutes with Ubuntu, Postfix, Dovecot and a domain name with at least one MX record pointing to that server - though obviously a pro setup would take slightly longer - a single domain SSL certificate and a couple of lines in config files to make POP3 / SMTP use TLS, SASL etc. where applicable, spam filter, webmail interface etc.
If you were having problems with this, then your IT department are unsuitable. If they threw you onto webmail, of course it's easier for them but someone, somewhere is doing the same job they should be and making a profit from you too. And don't tell your Data Protection guy that you have absolutely no idea who has access to those stored inboxs.