Have you been connecting to the router via wireless? I've experienced routers (mainly NetGears) that go into a slow state on wireless after a couple of days of heavy use, and restarting always solved this, but wired was fine. I would try and see if you are also experiencing slow downs via a wired connection. If it is just wireless, maybe it's time to get a new router.
To address the actual point of your original post (moving provider), I have recently noticed this:
http://www.aquiss.net/broadband-unlimited.php
They do a 12mbit connection starting at £20/month. I have no experience of Aquiss though but I think they might be up your street, as it is a fixed amount per month, unlimited (though I suspect being unlimited, they could possibly be attracting a fair few heavy users, and so may traffic manage, which may cause you issues for gaming). AAISP are also unlimited, but if you go way over your base amount per month, they will charge extra.
There is also BE Unlimited. Not been with them for nearly 5 years now. They were good back then, but I get the impression recently they may be losing their edge. My brother has 2 connections with them and has no issues.
Given you do gaming, I think latency is of more importance to you. At least with AAISP, who I am with, they do not over contend their network. The only contention will be BT - see
http://clueless.aaisp.net.uk/linkreport.cgi for exactly what they mean by this.