I dont like to denigrate other SEO guys, we all know theres good bad and indifferent, but if he can' nudge a keyword into the top 400 with a $200 budget, he is definitely not the man for you..
Rather than fire him and maybe cause trouble. I think it probably better to tel him you need to rethink your strategy. and will stop the SEO for a while, Thank him for his work, and say you will be in touch.
You.ve been a member here a good while. So look at the quality services, and in the meantime invest $50 on fiverr. theres plenty of threads here recommending good fiverr serivces., Unless you have monster competition, you should see some serp -mprovement