I know of no way that you carry out a company search based upon its registered address. However, if you note the names of the companies which mail is addressed to, you can check the Companies House register (free of charge) to see whether they've really given your address as that of their registered office. (NB: Only limited companies will be shown. Sole traders and partnerships don't have to register with Companies House).
Start here
http://www.companieshouse.gov.uk/index.shtml
Click on 'Use our WebCheck service'
Enter the company name in the top field of Section 1
Leave Section 2 as it is.
Click 'Search'.
You'll see the section of the alphabetical register which contains company names similar to the one you've entered.
To view a company's details, including the registered address, click on the number in the first column.
If you find anything amiss, notify Companies House.
Chris
PS: I can never understand why people moan about 0845 numbers. The cost of calling from a BT landline is only 2p per minute from 0700 to 1900 on weekdays and 0.5p per minute at other times (unless, of course, the caller has subscribed to a calling plan which provides free calls anyway).