Yes it is tough. If you do change ISP, need to shop carefully. Many ISP's in UK now shape p2p bandwidth. One of the issues is big business buying up smaller ISP's who retain their old name but use the parent company's policies or similar policies. So you may need to investigate to find out if in fact the ISP has a parent company.

Tiscali is a good example. They have spread their business europe wide including the UK.