When you're dealing with hundreds of thousands of 301 redirects you're going to probably notice some serverside performance issues. It is certainly an option, and if you don't see the site slowing down I'd use Chris's recommendation, including the messaging if possible.
But if you notice the site slows down significantly you could just leave the page up but dynamically add a follow,noindex meta tag in the header area, and show the message suggested by Chris on the original page instead of the old add. The message, of course, would link to the appropriate category to help them find what they're looking for. Users will no longer be able to get to that page from the search results, and I assume you'll keep those pages from showing up in internal search results too. The only way anyone would get to them would be a direct link, bookmark or some similar direct method.
This method would allow you to keep from having to do so many redirects, and would provide a good user experience. It would also solve the problem of having all of that old, thin content in Google's index and risking a lot of back-clicks or "block this site" clicks, which could bring on the wrath of Panda.
If you find that your old ads DO have a lot of links going into them it may be worth redirecting them so your category pages benefit from those links. Or you could use a combination. For instance, use my suggestion for most of them, but if you find some that have lots of external links you could redirect those on a one-by-one basis.