I heard a story on NPR a few days ago about http://www.catalogchoice.org/.  Maybe you heard it too. 

Supposedly you can sign up at the above web site with your name and address and tell them which catalogs you no longer wish to receive.  They say they will contact the vendor and get you off the mailing list.  I say "supposedly" because I have just gone through the process, so it is too early to see if it works. 

They have a FAQ page where you can learn how to cancel catalogs that aren't in your name (but sent to your address, of course) or are not in a variation of your name.

According to the guy NPR interviewed and the web site, "Catalog Choice is a sponsored project of the Ecology Center. It is endorsed by the National Wildlife Federation and the Natural Resources Defense Council, ..."

Hey, it's worth a try!  Those catalogs are coming fast and furious to my house these days.

-- paula

PS.  It's free.