Well, as a VM user (my father is the VM customer/subscriber - my part is maintaining the indoor setups etc), i've had no reason (from 512K through 50Mb options, over 5+ years) to want to change (based on if i was the subscriber, and my own usage experience). So i've no real 'god this is awful' experience to share and suchlike. I'd definately consider (for my purposes) going back to copper (dial-up or broadband, or ISDN) to be a major step backwards.
You don't strictly need a phone line (of any provider, BT or otherwise) to have broadband outside of Virgin Media, but clearly you will for fixed-line broadband (i assume that T3's etc aint in the running here, the scope is strictly domestic/business grade telephone line based connections i'd assume).
If you are in a decent coverage area, you still have the 3G/3G Mobile Broadband/GPRS option, using either a data-enabled cellular phone tethering or a dongle attached to a PC (also, remember, this doesn't discount router usage, as there are examples that will allow a fallback connection or primary connection via a dongle or cellular phone that's usb connectable).
At best, in reality, a cellular connection (based on a best case 7.xxMb connection, which is hardly stable for many where they are lucky to get around a 3Mb connection as typically 'fast') is going to roughly equate to poor grade 802.11 B/G connections (where, we should assume 'poor' means fundamentally unoptimised and nearer to dialup grade than broadband) so you'll be looking at throughputs of around 300K & 700K equiv throughputs at best, but of the real world 3G tests i have experienced, it's going to be somewhere between dialup equiv and narrow broadband (64K through 256K) equivalence - which in itself isn't bad given the circumstances and conditions and factors that affect radio comms links (especially since most domestic wireless data links use heavily crowded Ghz range frequency allocations).
I personally wouldn't opt for 3G Cellular over an available 802.11 link or any wired broadband in general, but would opt for it in situations where nothing else is available (on the assume of legal usage) or in a situation where it's a fallback role only for indoor use. I don't know if there are any currently available systems such as the old Hughes sat based system (the one that downlinked over a satellite link, and uplinked over dialup), so i'll discount that as a going viable option.
As for the limits and possible improvements to copper link technology (aka phone line based broadband) - that's pretty much a wait & see situation. On the whole, the actual limiting factors for phoneline based broadband isn't really exchange side (unless you are in a very poor location with huge contention issues, maybe) but more between the quality of the copper link between your location and the exchange, and also contention/demand at the ISP end.
Like with any 'copper' wired connection, the signal grade degrades over distance, so the further you are from the exchange, the worse any effect signal-to-noise ratio gets (where signal level drops, and there is more apparent noise as far as equipment/measurement would perceive) - which is really no different in basic principle to the effect of poor SNR in radio setups. Beyond that, the overall grade of the copper between your location and the exchange is equally important - you can't really expect a location with thirty plus year old copper to be as high grade now, as recently (say 5-10 year old) installed copper. Again, put this into context of radio, and you'll find it's the same story with radio antennas and the feeder (coax or balanced ribbon) - over time, through reaction to moisture, air and basic galvanic corrosion, the whole link degrades over time and even with top notch material, you get a basic worsening of SNR over a long period of time.
Finally, in terms of the external part of the copper link, there is only so much capacity on a telephony circuit (as is the case for fibre too), but the more connections you put onto the street copper (the under-street bit), the more the overall grade deteriorates across the street. It's a bit like what happens when you load an phone line with many extensions (each extension has an effect on the overall internal grade of the link, and each phone/device attached has a loading effect, pulling down the grade).
So i'd, in your shoes, way up whether you are prepared to gamble, or make do with the current situation - which is likely to be a worse move..?? - As for BT's fibre network, when it'll be up to a comparable coverage and grade - means having to wait til they've had a chance to get the work done (at the very least)
As for the VM billing issue - i'm sure the options are available on the Customer Zone part of the website, and if not - it's an issue that can only really be dealt with by talking to the horse's mouth (aka VM Customer Services).