My bargain basement registrar is godaddy.com. They automatically renew my domains on my credit card so I never have to worry, and they don't worry cuz they automatically get my money. Win Win.
GoDaddy, actually, is one of the worst.
Change your credit card. You will NEVER get your domain back without a LARGE processing fee.
--Shane