
An SEO company that takes money for nothing and fails to provide any evidence of work carried out...........never heard of that happening before.......not!!
I'm NOT saying all SEO companies do this.........I know a couple that are very good and would probably be very helpful to companies that know very little about the internet and how things like backlinks, anchor text, etc works but they are rare!!
As a business with a strong online presence we are routinely targeted by so called SEO experts offering to get us to a top ten position on search engines for many of our targeted keywords.......prices we've been quoted range from £300 a month to £900 a month and none of them included any 'onsite' optimisation.
We actually had one guy tell us he could get us to page one on google for HR Services and HR Services Scotland and it would only cost us £700 a month!

This guy must have been a real SEO expert......

..........He completely failed to see that we were
already ranking on page 1 of google, yahoo and bing for both of these keywords, and others, without ANY help from him or any other SEO 'experts'.
I could easily launch into a rant about SEO and Web Design companies who offer services then fail to deliver after taking payment of substantial amounts of money upfront (I know of many specific examples of this) but I'll resist the temptation and ask these two questions instead..........
1) Can you demonstrate a positive ROI for any investment in SEO? In other words, if you were hitting position one on every search engine there is, would the increase in site traffic result in sales revenues greater than the SEO spend?
If you can then engaging the services of a reputable SEO company is a no brainer.....if you can't, why would you invest £XXX a month when you'll never be able to recover the costs?
2) As a business owner, why agree to pay for SEO services, many of which will have actually already been delivered by a combination of the site owner's own efforts and natural progression via search engines? What is the actual 'value add' the SEO expert is bringing and YOU will be paying for and it the cost justified?
On a more general point, why shouldn't SEO companies carry the burden of the risk themselves and only take full payment when they can demonstrate results have been delivered?
I fully appreciate properly done SEO work, mainly backlink building, takes time and so there is a 'risk' to legitimate SEO companies if they don't take cash up front every month, but surely this risk could be mitigated with robust T&Cs, credit checking potential clients and taking a small (less than £100) retainer each month, only invlicing the final amount once the agreed results are achieved?
And before any SEO companies say they 'can't' do this for a whole host of reasons, let me tell you that many of your competitors have seen the light and ARE doing this or something like it.........like this for example.
/back to the question in the OP/
In this particular case, I would echo what others have already said......insist on a detailed breakdown, including evidence, of the work they claim to have done and when they fail to provide it, immediately challenge them and contact a trading standards AND a good solicitor.