click here This is an example of the Yahoo submission process. You will notice that you do have two choices & the vast majority of people will use the free service. So it may take alittle longer to get listed, but as you've already pointed out if your website is designed correctly & you endeavour to get external links established etc high ranking's can still be attained.
Most if not all of the major search engines will have the ability to submit to their listings.
The most important thing to consider when paying a company to submit on your behalf is that your website will be submitted to the correct type of search engines, after all you want to make effect use of your visitors.