Specific answers to your questions followed by an explanation:
1. Does this sound like a good solution.
No. AnywhereMap is great, but not in Europe.
2. I can't for the life of me find a site which explicitly sells the Europe/UK Anywheremap. Anyone know. Can I get it "cheap" from the States?
But it direct from them. There are no region-specific versions.
3. If I get the AnywhereMap, is there anypoint in getting the CAA digital map for £50 (given I've got a hard copy in the cockpit).
Yes, because AnywhereMap is not very good in Europe.
Explanation:
AnywhereMap is a great product, but the European database really lets it down. In the US the database is updated every month, but the European one is years out of date. Even when it was not it is very limited - many (most even) popular GA airfields are completely missing along with all their associated data. Unless you want to add a lot of waypoints by hand (and then only have them as waypoints rather than proper airfields with extended centrelines and such like) it is pretty much unusable in the UK. They have been promising an update with a more comprehensive database the whole time I have owned it - about 2 years.
If you still want to go ahead with AnywhereMap you can buy it from them directly, using a credit card. You don't buy Europe or the US specifically - you get both and the whole lot can be downloaded from their website once you've paid your money and get given an access password.
MemoryMap navigator is great for seeing where you are on CAA charts but not so good for planning and navigating a route and it lacks many aviation functions that you may (or may not) find useful.
I almost never use my iPAQ/BT setup in the plane in the UK - I prefer a Garmin 196. If I do use it I run MemoryMap.
For road navigation TomTom is really excellent (much better than a Garmin 196). I wish someone would make a piece of aviation software as good in quality as TomTom is on the roads.