As you've mentioned Mio have a look at the Mio 168 here on this site
http://www.totalpda.co.uk/Mio-168-GPS-Pocket-PC.aspx
They also have bundles with destinator or Mio mapping. TomTom appears to be the most popular. If you decide on TomTom there are two sets of CD's, make sure you get the one marked FULL software and European mapping + GB.
If you don't need Street level maps in Europe you could go for the GB maps plus Major Roads of Europe. However, should you need say France and Spain, it's cheaper tp purchase the full software as mentioned above.
If your car has an athermic windscreen, you may find the Mio A201 is better, although can be a bit fiddly to get TomTom working.
I have the Mio 168, as does my son and a friend, two of us have athermic windscreens and find it's best to get a lock on the satellites whilst standing outside the car before setting up inside. It will lock on sitting in the car but takes much longer.
You should get MS Activesync with your Mio CD but may need to download from MS for you Desk/laptop. When connected Calendar/Contacts/Tasks etc will be updated between the two.
Don't forget to take into account something like a 1GIG SD Card so there is plenty of room for music/pics etc.