It depends on the size of the site. Paid inclusion (per URL) is best for smaller sites. Trusted feeds are best for large XML based sites with many different products. You would pay per click on these.
Paid Inclusion sites off the top of my head:
1. Inktomi 2. Ask Jeeves 3. Altavista 4. FAST
Go for Ink first as this will get you into MSN and into Yahoo at a later date (most probably). I would also go for Ask Jeeves/Teoma because the free route seems to take months to update. Altavista - maybe, maybe not. Same for FAST really. If you are being spidered already there may be no need to use PFI.
Lots of success :) It just depends what you budget is.