I'd go to 123-reg.co.uk and feel pretty sure you could forward to your existing Hotmail account (or download from the Hotmail account with Thunderbird and send via your ISP, if they allow you to send with your intended domain-based mail address).
If you forward to your existing Hotmail account it means everything will be in one place, too. There's no real advantage in having the mail saved online - nearly all services have times when they are doing maintenance, so downloading it, and/or forwarding to some other service, is often better.
I'm not sure about all the hosting/ domain registration firms, but in the past I've used a number of web hosts and relatively few have multiple mail servers. I have found from experience that when there is some problem, they may take a web host (and associated mail service) down for hours, and that's when a client (or in my case, clients, of my client!) gets an error message. I've been using a reseller account with Xilo, which I know has a cluster of mail servers and has been very reliable in the time I've used them (a few years now), compared with various other hosting firms.
E-Mail was always a 'send and forget' service, and in days gone by, it might have taken a week for a message to get to Australia, for example. Nowadays, people seem to go ape when they have not had a reply within 15 minutes (and unfortunately the mail services getting overloaded, especially by spammers, make that more awkward). I cannot re-educate my clients, but personally I don't fret if a message takes time to get a reply - what is more important to me is that it does not get 'bounced' because a server isn't reachable, and that's where Xilo scores, being a UK based ISP, and one that is a bit smaller, and more technical than many of the 'big 5' (where the big 5 have millions of customers and tech support is either in overseas call centres, or takes a while to get to someone senior, when there's a real problem)... In addition, I think the big 5 give much greater importance to collecting their monthly payment than having working e-mail (!)