You can literally mail an envelope of cash to them and they'll credit your account. Probably the best way to remain anonymous. At worst, they'll have the zip code from where it was mailed from and potential fingerprints. But since an envelope isn't really a financial record, I doubt they would hold onto it.

Okay I think I just misunderstood. I guess I was assuming "paying for the service anonymously" meant "paying such that the person using the service is anonymous", not "anonymously paying for the service". Haha. Syntax is fun!