Well I've been on the medium package for TV for around 4 months and on demand has always worked fine, even now they are advertising it as part of the medium pack.
http://allyours.virginmedia.com/webs...ct.do?id=11169
"Virgin TV on demand where you can choose from a massive library of films, TV, music to watch whenever you like"
The catch up still works just tv choice on demand, it won't even let you buy anything.
Edit: Just found this.
TV Choice on demand - Included with TV Size: XL, available for £7 a month with TV Size: M and L
Complete series to watch at your leisure - you can even watch them all in one go! Includes favourites for everyone such as Grey's Anatomy, The Sopranos, Life on Mars, Postman Pat and Planet Earth.
Nice of them to advertise the change :o