Microsoft have just released MSN Local Search. By clicking the
local tab on the MSN homepage you can test this new service (currently in its beta stage). The service allows you on type on a service or product you want to find, for example "book store". When you click "local" is then lists the top 10 stores (labelled A-J) in order of distance.
For each listing it provides business name, address, phone number, distance and even directions. All this is nicely displayed on a map (see below on my rather small screen capture). The maps are quite basic but do allow you to zoom in/out and pan without reloading the entire page (much like
Google Maps without the scrolling.)

You location can be altered in the settings screens in case it is incorrect first time - unfortunately I couldn't get it to work of UK results I had to move my location to the US to get results like one screen shown above. Microsoft are currently working on Virtual Earth to directly take on Google Maps later this year.