My wife is horribly anal about this kind of stuff....and I'm glad she is. She gets about a million fvcking catalogs every week, from companies we've never heard of. Almost all of them have her personal info pre-printed on credit apps and/or order forms. She saves them all, then once per year, she has Shred-it come in and take care of it. We have a simple home shredder we use for the daily crap, but the bulk stuff like magazines and all the bs junk mail, we actually pay someone to shred for us. (gawd, if we tried to shred everything, we'd go through home shredders on a monthly basis.)
BTW, YES, she's called and tried to get off the mailing lists, but it seems like everytime we do, they just sell our info to another list, and we end up getting MORE..