www.yell.com if you know the company name and town.
www.streetmap.co.uk to find the location by postcode or address.
www.royalmailgroup.com to get an address from a postcode and vice versa.
www.routeplanner.rac.co.uk to find routes and distances.
Had a look at the GMaps API a little while ago for integrating it into a customer management system and it's very good. Only problem is when you start searching for company names and getting two results...
http://code.google.com/
This is probably more relevant to your needs
http://code.google.com/apis/ajaxsearch/local.html
First result for "post code map london"
http://www.londonbaptist.org.uk/london_postcode_map.gif