I want to build a website where you can search by entering the postcode (UK). I know that RoyalMail owns the Database to do this (it's only very expensive, $100K). What are my options?
You can now get Ordinance Survey postcode data free of charge at http://www.ordnancesurvey.co.uk/oswebsite/opendata/
There's an alternative service that allows you to access their data with an API: http://www.geonames.org/export/web-services.html, or download the data: http://www.geonames.org/.
I'm not entirely sure how usable or complete their data is, though.
We've been using AFD's web services for UK postcode lookup for a number of years. They offer various online products, some of which may meet your requirements: http://www.afd.co.uk/products.asp?expand=Internet.
I can't comment on the cost as our client holds the contract with them but I believe it depends on the usage level and, at least in a commercial context, isn't all that expensive.
$100k is way over the top - for a website you can have RoyalMail data directly from them for about GBP6k. This is for unlimited annual licence including data delivery. You would have to register as a reseller and enter into a formal contract.
Our company CraftyClicks resells the PAF and for most people buying from us ends up costing LESS then going direct to RoyalMail.