I don't know about the UK, but if you want to keep things in Europe then I can vouch for Netim in France.

INWX in Germany also seems well regarded but I haven't used them.