My understanding is that what is relevant is the Tax Point. This is the date at which the service is deemed to have been made for VAT purposes. In turn, HMRC define this date to be the earlier of either
The date written on the invoice
The date when the services are deemed to have occurred
If you have an invoice which has been sent to you 'in advance' for convenience and the date written on the invoice is January 2010, there isn't much you can do - I do not believe early payment impacts the HMRC interpretation of the Tax Point - and the business supplying the service to you will have to account for VAT at 17.5% so will correctly want to charge the 17.5% figure.
If the date on the invoice is November 2009, VAT charged to the invoice should be stated at 15% - even if the service isn't delivered until 2010. Phone them up and point this out. You need a new invoice with the 15% figure on it - you can't just pay less than the invoiced amount.
Energy (electricity, gas, heating oil etc) has been VAT rated at 5% for many years now. This isn't new.