After exchanging a few emails with the registrar (it took a few before they actually listened to my problem instead of glancing at it and cut-n-pasting a packaged response), they let me do a transfer to a new account for twenty bucks, inclusive of renewal. So my domain is no longer expired.
I went and found a new host based on some recommendations I found – a little more expensive, but I get a lot more space and bandwidth for my money. Not that I need it, but it’s nice to have.
And I called my credit card company and had them reverse the charges to my original host.
So (knock wood) once the new DNS propagates, all should be well with the world.
I’ve had great success and service from Joker.com, and I own about six domains (I think, I lose track). They charge 12EU for a year, but they also give you services that other registrars don’t, all maintainable through a nice web interface. I moved all my domains off of Network Solutions/Verisign, Roxio, GoDaddy, Melbourne IT, and so on to Joker.