Forum Moderators: open
Yes the paid submissions are worth your money. The major directories you would pay for are Yahoo and Looksmart. You also need to get into DMOZ. DMOZ is a human edited directory, so they are usally search engine optimizers and know the tricks. Yahoo and DMOZ can be hard to get a good description in, but it is possible. Know this that in both of them you most likely will get your description butchered, so keep the description down to 1 sentence for DMOZ, as for Yahoo you want to use about 5 to 10 words to describe you company.
Either way, paying for a Yahoo and Looksmart listing is, IMO, very much worth the money.
Remember, you can always start out small, and hire the big guns later...
Paying for Yahoo is a must for obvious reasons, but even more important, IMHO, is a LookSmart / Inktomi combination.
Between the two of them, you ensure you a presence, to some degree, in LookSmart, Excite, MSN, AltaVista, AOL Search, iWon, HotBot, GoTo, Goo, About.com, Anzwers, NBCi, and Canada.com.
Throw in ODP and a PPC iniative, and you've got just about everything covered.
First thing:
Paying for search engine submission is a separate issue from paying for listings in directories, and paid services like GoTo.com or Inktomi paid submission, for which you've been given the list.
Do some reading here at the board prior to making your paid submissions, particularly in choosing your keywords. Also, read whatever you can find on how to make submission to directories. With Yahoo it's $199 to be considered, whether you're accepted or not. Make sure and choose the right categories and read the instructions prior to submission.
You are also asking about paid search engine submission services.
Are they worth it? Not in my opinion, they're not. I never have used one and never would. It is not the submitting that will get rankings - it's optimizing your site that's the important thing.
You need the directory listings, and only need to submit to the major search engines - after optimizing your site. No need to submit to hundreds or thousands, that's a waste. And do the submissions by hand.
Dig in and do some reading. Here's a good place to start - it's an excellent step by step "tutorial" that explains the basics of how to design a high search engine rankings web site: