Paid submission always. A good listing here is the "bread and butter" for any website.
>>>Inktomi (should you submit all of your optimized pages or your 'best' pages?)
Paid Inclusion: Small sites - every page. Large sites - unless you have the budget, just stick with your most important pages.
>>>Ask Jeeves/TEOME (do you typically pay for submission here?)
In my opinion, a waste of money. I have several sites ranked very well here and see almost NO traffic at all from here. Your results may vary.
>>>Altavista (too much money? What do you think?)
Again - waste of money. Very little traffic from good rankings. At least you can get into AV for free. Just use free submission form.
>>>How do you go about establishing link popularity? Do you get clients to find possible sites or do you find them for them?
If your clients can help you find good sites to link to, encourage them to do so.
My technique is usually this to start with:
1. I identify my main competitor's websites.
2. I use the backlink feature on Google to find out which sites link to my competitors.
3. I request links from those sites.
If they will link to my competitors, 9 times out of 10 they will link to me also.
Also, be vigilant about getting into ODP.
It may take a while, but is one of the best ways to boost link popularity and increase traffic.