Geonames offers a free online geocoding service, and this can be used for the the first part of a UK postcode, giving a result that is in the general area, in XML format. Eg.
http://ws.geonames.org/postalCodeSearch?postalcode=fy8&maxRows=3
You can also download the data they have collected for your own use here.

Another online geocoder is at http://emad.fano.us/blog/?p=277

Here is an interesting post on using the Google AJAX Search API to geocode on the fly. Their own map uses this method, and very nice it is too.

Mapstraction is a project to bridge the gap between different APIs and make it easier to switch between them.

http://mapperz.blogspot.com/ reviews different map services and new developments.

Finally, I noticed the Yahoo maps api terms and conditions don't disallow use with private sites, as opposed to Google, but they also leave open the option that Yahoo could decide to charge for their use later.

Updated 28th Aug 07:

localsearchmaps.com offers a free uk geocoding service.
See the result of this for example...
http://geo.localsearchmaps.com//?zip=fy8%203qx&country=UK&use=google2&format=txt
Just substitute fy8%203qx for any postcode.
You could grab and use this data via PHP (see http://forums.digitalpoint.com/showthread.php?t=54945 for details - the post by tops30 near the bottom)

In classic ASP you could use a variation on this...

url = "http://geo.localsearchmaps.com//?zip=fy8%203qx&country=UK&use=google2&format=txt"
set xmlhttp = CreateObject("MSXML2.ServerXMLHTTP")
xmlhttp.open "GET", url, false
xmlhttp.send ""
Response.write xmlhttp.responseText
set xmlhttp = nothing