Had a similar problem with 3 (Three) once. Ordered a contract that included a free phone (only a £20 a month thing). Never arrived, but the bills kept coming.
Phoned them up, told them the parcel had *never* arrived, they confirmed the phone had *never* been activated, never been used, but I insisted that they block the IMEI number, SIM card, etc. because it was technically lost/stolen (and the cheeky bastards said it was *MY* responsibility to chase up the parcel with the Post Office - not when I never received it and the Post Office tell me that only the sender can make a claim). Next month, another bill. Phoned, argued. Next month, another bill. Phoned, argued. They wouldn't stop the bills or they said they would and never did, so I just took matters into my own hands.
At that point, I just cancelled the Direct Debit, reported them to my bank with an official Direct Debit complaint (and the bank then swiftly cancelled all recurring payments and refunded all the previous payments immediately). Amazingly, a day later I had a phone call threatening me and charging me for cancelling the Direct Debit. Then the next week (seeing as they *couldn't* get any money out of my bank automatically any more, and I refused to pay anything for a phone I'd never received and couldn't use even if it turned up tomorrow) they phoned up and tried to "resolve" the matter (which meant that they forget all about the charges and might "let me" waive the various things they'd charged me for).
Mistakes are fair enough, but Three were utter pillocks about it all and couldn't see sense. I refused to take their calls after a while because I was tired of the accusations and going in circles, so I demanded they contact me only in writing. That way, I could have evidence of their incompetence should I decide to take it to court. Twenty minutes later the same person called me back three times in a row, and got hung up on each time.
They completely failed to fulfill any of their side of the contract (deliver a phone, provide a SIM card, provide telecoms service, supply me with new ones when the originals were lost / stolen / blocked, etc.), so I was happy to take it to court. "Your honour, they say I haven't paid for a phone that I haven't received, their own records say they've never seen come online, anywhere with any SIM, the phone/SIM wouldn't work on any UK network anyway, it's marked as stolen property, that they didn't obtain proof of postage and/or proof of receipt for, which *I* reported as missing the same day as their '28 days for delivery' note expired and which is in a box which contains the paper contract which I needed to sign in order to agree to this contract and authorise the payment by Direct Debit".
I think that'd be a pretty open-and-shut case. That's probably why they gave me my money back and I've never heard from them since.