Free submissions have netted us good positions in AltaVista, but traffic drive is minimal to say the least. In fact, it would probably be a couple of months since the logs showed any referrers from AV.
Money better spent elsewhere methinks - preferably on paid submissions to Ink, Fast & Teoma. If you're already submitting to those, save the cash & put it towards a goon night out! :)
I'd say never use the AV pay for inclusion. We'll use the feed program which nets almost no traffic but since it's PPC for larger sites they don't get taken to the cleaners. It's not worth the trouble of setting up a feed just for AV either. If yer gonna do Ink and the vendor you go through also offers AV its minimal extra work to send it to AV also.