I really hate the term SEO as it is so yesterdays word. A GOOD web marketing company should
1. carry out extensive keyword research (i regularly end up with a few hundred phrases for a small site, shopping carts can have thousands)
2. run a PPC campaign to be used as part of the keyword research and also as a fall back/kick start to the site.
3. overhaul the site structure and arrange a redesign if needed.
4. ensure no traffic is lost by using redirects (301) from old pages to new.
5. ensure the site validates
6. ensure the copy is well written or re-written
7. ensure the site is designed to maximise conversions
8. ensure usability best practices are employed
9. ensure the site complies with the current laws (8 out of 10 site possibly higher do not)
10. most importantly, ensure the site has no technical reason for not working, such as slow server, poorly set up server, use of frames, use of bad dynamic urls, use of poorly constructed query strings on dynamic sites, content hidden too deep in nested tables etc.
There are many many more, and these are just off the top of my head.

Too many snake oil salesmen that call themselves SEO's operate online. They do not have a clue about stats packages, the workings of the algorithms, how search engines and directories work, usability, accessibility, conversion tracking, maximising conversions, or anything else. ALL they know is how to get backlinks to a site, and bomb it to the top of the search engines. This is hardly optimisation is it!

Optimisation is taking something to its optimum, optimum quality, optimum ranking, optimum conversion, THAT is search engine marketing. Encompassing all the aspects of marketing online. NOT just getting a bag of bones to number one on the search engines.

If you want to know the sort of difference high quality work can make, this is what happened to a client we took on this time last year.

They were a shoestring S3x toy site, turning over £4000 a month, mostly through PPC (the rest was offline marketing and repeat business). I worked with the owner, who did the design and donkey work, and within 6 months the site was making £10,000 a week! conversions were optimum, and the average sales value had shot up as we used prompts to encourage the visitor to spend more via offers and package deals. Repeat business sky rocketed due to email marketing. I better stop now as I am ranting LOL, and I have to be up early in the morning as we are off to London to see the lights being turned on in Trafalgar square over the weekend, climb the monument, and visit Hamleys, the V&A plus the Natural history museum. (Lottie my 6 yr old has set the itinerary)