v9 has an integration with Postcode Anywhere built in. Go to 'Settings | Business Settings | Address Lookup'.
It is now a requirement of Royal Mail that you use different keys for the 'Invoice Address' and 'Delivery Address' lookups.
Pre-v9
Mole-End software have developed a plug-in for incorporating 'Postcode Anywhere' into your store. This is a system available in the UK where a customer can enter their postcode, and the rest of their address details will be automatically populated.
The URL for the solution is:
http://www.mole-end.biz/acatalog/PostCodeAnywhereDef.html