I can’t remember where I found it, so I thought I’d put this here so I don’t loose it!
In user.js or about:config, find mail.addr_book.mapit_url.format and set it to:
http://www.multimap.com/map/places.cgi?addr2=
@A1&addr3=@CI&pc=@ZI&db=GB&client=public&
cname=Great+Britain&advanced=true&mapsize=big
Or for streetmap use:
http://www.streetmap.co.uk/streetmap.dll?
postcode2map?@ZI