I understand your pain and I think that you have the right to ask what's your money is worth.
The first problem is that there's lots of crap info about SEO and, although SEO does help with your rankings, nowadays there are even more variables into the mix that do not involve SEO (such as social media and the creation of good content which is SEO related but not necessarily and of course, pay-per-clic and banners, which is online marketing but not really SEO)
The second problems is you. The thing is that you don't trust this company. And without trust, there's no way that this relationship is going to work. Not even if he's a true expert.
It is also true that you have had bad experiences in the past and that you are a bit (maybe not a bit) suspicious about the whole thing. And this guy is not going fast enough for you, showing you what you already know.
So there's a possible third problem: that this company is not as good as they should.
In my opinion, no matter if they're truly professionals or not, you should step back and get your money back simply because you don't feel like you can trust them.
I understand that this company will want you to stay. After all they're a business and a business is about getting cash from the customers. But if they're a bit smart, they will let you "go". With this, I mean that they will ask you to stay, you will say no, and then they will refund the rest of the money.
After that, they should send you informative e-mails with some tips that may help your site or with their stories of successes so you can be sure that they know what they're doing and that they do not fool around.
That's, at least, what I would do.