I use UK2 and have done for about 25 years...(nearly) all my domains are registered through them so having hosting in the same place sort of makes sense and I hadn't even considered moving hosting company. Probably because it sounds like it could be a faff - I shall look into what is really involved, or I might just bite the bullet and get a VPS!

Yes, moving domains around isn't always the easiest thing. Note that there is no technical requirement for domain names and web servers to be hosted by the same company (sometimes there are contractual requirements), that's how I do it - keeping the domain registered through a well-established company means that switching hosting providers doesn't require domain transfers. OTOH, having an all-in-one provider is of course nice too, provided they actually offer the services you need, which your current provider doesn't really - installing a newer Perl isn't shouldn't be a big deal.

choices, choices and more choices...

Very true... I could of course tell you a few hosting providers in Germany (Strato is a big one and from Berlin.pm I know there are a few Perl guys working there), but unfortunately I don't know about the UK.