Fair point, I only use the registrar for DNS (and registering the domain obv). I use United Hosting for general Web/email hosting (not much of the former). They're not the least expensive I've come across, but have really good support and are reliable (based in Sheffield I think). DNS for some domains is hosted with them.
A couple of the domains have email hosted on Google apps. Apart from the initial setup (which involves adding a TXT record, presumably so they can confirm admin is in place) it just works; not cheap but does provide Exchange ActiveSync, and has a 99.99% uptime SLA. (And is ad free.) I've never encountered any routing or performance issues.
The .uk hasn't entirely been by my choice, but agree that Nominet make things unnecessarily complicated! I don't usually need support at all, except when they lose one of my domains! Now I can't resolve it, they're not responding to support tickets, emails, or twitter, and I can't phone them.
I have two problems with the current registrar: they haven't registered a new domain for me, and they have somehow 'lost' one. And they have stopped communicating.
A friend on FB has recommended Monster as well. It's not my day job (just manage domains for myself and friends/family) so I don't need a lot of hassle. If a registrar can register the domain properly, maintain the DNS correctly, and let me make changes when I need to, then I'm happy :)
I'll look at all the suggestions and aim to find one in the next few days. I've really had enough of the current registrar!
Really appreciate the input :) I'm guessing this is your day job 