営業代行を債務不履行で中途解約したい

法人です。
1年間の契約で営業代行会社と契約を締結しましたが、ターゲットに対する仮説、トークスクリプト作成もイマイチで、リードの獲得として出してきたものが、無理やり資料請求を取っただけで、相手先は資料請求をしたことすら覚えておらず、全く興味がない状態でした。

さらに、新たなアタックリストを提示してきたものが、以前、リストから外したものや、リードとして出してきた企業を入れてきたため、重複チェックもしていない状態です。

現在、4ヶ月目で解約をしたいのですが、「理由の如何を問わず、利用期間中、利用契約の解除・解約ができないことについて、承諾するものとします。」という規約をたてに解約できないと言ってる状態です。

当社としては、債務不履行だと考えていますが、解約は可能でしょうか?

契約の内容次第ではありますが、契約上の義務の不履行がある場合であっても解除権の行使を一律に排除する旨の規定があるのであれば、それが不当なもの(契約当事者を一方的に不当に拘束)として民法90条等を理由に無効主張できる可能性があります。
解除権行使の制限が無効であれば、理屈上は債務不履行により契約解除、という対応もあり得るかと存じます。