I understand that Loredan, an arm of the Company I work for does SEO and are pretty good at it too. We don't charge anywhere near these prices though and even taking into account time and effort we'd find it hard pushed to justify charging that much. But as you pointed out, some will pay that so perhaps we'll re-evaluate our costings.
the keyword is just too competitive, try something like: quality business directory, uk business directory then it will be a much cheaper and easier to target. Tips: Do link building as many as possible, rather than spend $2k per months for seo only, spend for link building and promote in forums.