My knowledge may be a bit rusty as it's been a few years since I was involved in premium SMS, but..
The onus is on the service provider/sms aggregator to prove that you authorised them to send premium SMS messages to your phone. Usually they can see this by looking at their records for an inbound message from your handset requesting the service (and therefore agreeing to the charge).
If it's a subscription service, you should have received a free SMS confirming the subscription, and then another one once a month (or when you reached £20, whichever is the earlier) reminding you that you've subscribed to the service.
Now if you're 100% sure you never agreed to this, give the service provider a call back (I'm assuming this is who you spoke to?) asking for details of your request to use this service.
If they find a record of your request, and can provide a bit more detail, (which 95% of the time is what's required to jog peoples's memories) and you suddenly remember you did use the service, then all is good and lovely. If they can't, or you're really adamant you've never used said service and you're sure the dates and times of any messages requesting you join/use the service don't match the time when your mates/family/dog could have swiped your phone when you weren't looking (again, it happens!)
then the person running the service is a little trouble and you should contact PhonePayPlus (the UK's premium services regulator) and lodge a complaint.
http://www.phonepayplus.org.uk is a good place to start, if you tap in the number you'll find the contact details for the service provider - plus there's a link to register a complaint if you wish to do so.
Good luck, let me know how you get on..