ODP takes your listing for free, puts it in a category (perhaps two) and then forgets about it. For odp you do not need any outgoing links. You also wont see ODP referrals as such, since many dirs take ODP or a subset of it. You'll see the referrals from strage sites, until you realize that they have taken a part of ODP.
Yahoo will take your money, put you in the category you want, list you there as 'new' for a week (before all others), then alphabetically. The bigger part from referrals from yahoo will come from searches, after this week, not from you being in a certain category. Again, no questions asked about the structure of your site.
Altavista and Google, otoh, will look for link popularity, but they'll count incoming links, not outgoing ones. Again, no need to point towards them.
No idea about NBCI/Snap and About. atm I dont get referrals from them.
Just a word about feasability to pay for inclusion. Recon that eg. 1% of traffic is actually paying customers, or customers who provide feedback. Now, since I am listed in Yahoo, my traffic has more or less tripled. Means I get 3 times as many requests. Now, if I sell blue widgets for USD 5 apiece its clear I need to sell considerably more than if I sell red widgets for USD 2500 apice, to pay for a submission. But just look at it as 'marketing cost', with a payoff in mid- to long term.