I've stopped using 1&1 after several problems. Some of them were inadvertently my fault, as it turned out, most of them weren't though, and one of them involved my site MySQL database going AWOL for some weeks and when it eventually did return its content was gone.
Letters such as the one you received are normally automated, which still doesn't alter the fact that if you paid your bills you shouldn't have received one to begin with.
It's not very inspirational is it ?
Frankly I can't offer any useful advice that you won't have already considered yourself. I'm sure you're unimpressed enough without me trying to teach you how to suck eggs by suggesting the usual phone calls and so on.
About all I can say is good luck.