ネットの会社との契約をやめたいのですが、可能でしょうか

お世話になります。
SEO会社との契約について悩んでます。
昨年11月末に大手でネットショップを開設いたしましたところ、SEO対策をしているという会社から営業の電話がかかってきました。
グーグルやヤフーの検索でワードから弊社ショップを上位表示させ、売り上げに貢献するという内容でした。ホームページと過去に手がけた方のページを参照として教えてくれ、売れなかったことなど無いと豪語されてましたので、それならということで契約いたしました。
ところが、2ヶ月たち、3ヶ月たちましたが、気配なく、別のbeingという検索エンジンでは、何ページかに上がった画像が1度だけ送られてきましたが、グーグルやヤフーでは一向に表示されないので、何度かメールや電話で問い合わせして、こちらで修正するべきことをしたりしてました。
それでも上位にあがってこないので4月に電話したところ、ショップの仕様が変わったので難しいので、別にホームページなどあれば、そちらを対応させていただくことと、検索ワード変更は可能ですとの回答でした。
それだと、初めからホームページを用意する必要も出てくるので、支払いやめたいと申したところ、契約は2年あり、解約出来ないとのことでした。よく契約内容を確認したところ、成果が出なくても解約出来ないとか、解約する場合、残期間まとめて支払うとか、その当該成果を保証してないとか、かなり一方的な内容には感じました。
このまま、何も結果が出ないまま毎月カード引き落としだけされてくのも嫌ですし、新たなページで頼むのも頼みたくない感じには、なってるのですが、どのように解約したら良いでしょうか。
ちなみに、このSEO会社を帝国データバンクで調べてもらったところ、住所から検索した、会社名、代表者名はヒットしない会社だそうです。株式会社を名乗ってるなら登記があると思うのですが。
契約書はメールで送られてきており、契約内容に受け取ったら受領と同じというような文言が記されております。

弁護士を通して債務不履行解除の通知を出してもらい、一部の返金を求める交渉をさせることが考えられます。消費者問題を手がける弁護士の方がいいと思います。