Receiving spam to addresses I've never shared

Hi,

I've always used a catch-all email address so that I can create unique email addresses for everyone I deal with and then monitor who is sharing my details.

For a while now though I've been getting spam to addresses that I've never shared with anybody else, addresses that I've only used to test a form on my own website for example.

Although I can't prove they're responsible the only common denominator here is my host company, Dreamhost. Their email servers are the only ones that would have ever "seen" these addresses and therefore know of their existence.

I think I'm going to have to change hosts anyway, so I have three questions;

1) Can anybody recommend a UK based hosting company that offers similar value to Dreamhost (i.e. unlimited websites, domains, bandwidth etc)?
2) Has anybody else experienced this issue?
3) Is there any way to prove or confirm Dreamhost's culpability and what redress options might I have?

Incidentally, I know that by using a catch-all I'm open to receiving spam by people simply guessing an address, but that isn't what's going on here. I'm only receiving spam to addresses that I have actually created, just never shared with anybody.

Many thanks in advance for your help.