Hmm, I guess its going to depends on A) the provider and B) your set up?
When you say VM had support for Linux, what were they supporting? I only ask because really if they supply a modem and you supply a wired/wireless router to attach to this because you have more than one machine in the house then I don't see what is needed from any ISP?
I recently got VMs 50Mbps service; they provided a modem and free router so they set those two up and left, there was no interaction with any of my machines from their engineers. The demarcation point was their equipment, beyond that it's nothing to do with them (and as with most of these things, its plug and play). I guess though if you do have one machine plugged strait into their little black modem boxes it may be a different story, was this your scenario? Although again I can't see what was needed, shy of setting your machine to use DHCP (which you can bet your bottom dollar is the default configuration anyway) I can't imagine what they would want with it?
Any provider like BT or VM that chucks in a router shouldn't be bothered by the fact you are on Linux. If they are providing the router then that is where their service ends. If your Linux box has difficulties connecting to the Internet but the router provided is defiantly working then it is your responsibility to get your Linux box working. The only time they don't like it is when you ring them seeking technical support and the problem is with your box and not their equipment because the call centre monkeys aren't clever enough.
Have you got any idea who you are going to move to?