i employed an SEO "specialist", he charged me £250 a month for the first 3 months, my website went onto the first page of Google within 3 weeks and stayed there for the most part for the whole 3 months, at the end of that set-up period, my SEO guy said your website is easy to keep "UP" as there is a limited challenge for position, so I can keep your listing on the front pages for £50 per month as there are few hours involved. I have now been "up" for 8 months, traffic has increased and sales climbed dramatically, my SEO costs dropped and I have recommended him to about 22 companies, all reporting good things... so SEO in the right hands works, and with the right business model seem an easy business to grow..
The hard part is finding the right guy, mine was recommended to me by a business friend who had also been using him for a number of months.. So qualifications as an SEO should really be more "how many companies already recommend you"...
Buying wise is always key, forums like this one are a great help and I recommend you use them as much as possible...