Muckshifter,
Couldn't you just tell your credit card company that any future requests for payment from PayPal should be refused? I don't know, but surely a cardholder has the right to stop automatic debits going from their account, in much the same way as a Bank account holder can?
OT - It's a really nice spot, so nice that I'm not doing what I should be doing
Quadophile
Your story sounds dreadful and I imagine it could quite easily happen again. I know some credit cards, Capital One is an example, make a big deal of guaranteeing that if your card is used without your knowledge or permission, you will not be held responsible. Under UK legislation you already have this protection, but if you have to resort to it then it could take a long time to resolve, as your experience shows. If the cc company make the specific promise to protect you in such an instance, I would guess the matter would be resolved much sooner.
Credit card companies obviously want to reduce fraud to a minimum. They will not mind at all if you contact them, say every six months and ask for a new card with a new number. For them it's a much cheaper option than (a) losing a customer if they refuse and (b) they have to pay out on fraudulent use of your card. It's also a bit inconvenient for you, but it's much better than the potential hassle of someone eventually getting hold of your cc details and using them fraudulently.
OT - Dumb n00b question. How do I do quotes like you guys?