I used to call every company that sent me spam mail (I got them from target, sephora, ulta, safeway, yellow pages, ISPs, citi, etc... pretty much everywhere) and I never once had a single company stop. Like you, I never signed up for any of them, I just started getting them. As far as I can tell, there is literally nothing you can do to stop them. Some companies will pretend to take you off their list but don't be fooled, another letter is coming soon...

One thing I've heard is that if you mail back junk in the prepaid letters they'll stop since they have to pay for it, but I never bothered trying so I can't confirm that.