Ordnance Survery produce free maps of UK counties and regions. They say you can not use them for financial gain, but can use them for presentations and graphics applications, so I think that covers what you would be doing. I read it to mean you cant sell the maps basically.
Free downloadable GB maps from Ordnance Survey
If you have a map like that, then it is quite easy to do the effects like you have shown, using a simple html image map with rollover effects. You do not need to use Flash and Flash always has the problem of not being very indexable by search engines.
Image map - Wikipedia, the free encyclopedia
Your question took me right back, as the first website I ever built back before 2000 was for my dads pub letting business and it had an image map just like the one in the site you linked to. I just checked it out in archive.org, brought back some memories.