|No such thing as a small change|
An interesting problem and one which I've had to face!
My ultraparanoid assumption is that any internet connected machine can be hacked by a sufficiently skilled and determined cracker. Remember that someone really serious might come after you. If you have 100,000 live credit cards in your database this isn't script kiddie territory this is organised crime territory...
Anyway enough paranoia. I think you've got two choices.
2) means PGP with the secret key on your isolated back office machine. This doesn't mean you can't automate the rebilling process just that it will be done from the back office machine. Nothing else is good enough - a symetric cipher (like blowfish etc) is worthless since the key will be available to the webserver. Same with the hashing scheme.
PGP with the public key on the webserver and the private key in the back office is the only way to make it work cryptographically speaking - you need an asymetric cipher to satisfy 2) and RSA is the best method at this point in time. If a cracker came in and owned all the internet connected stuff they would have to crack a 2048 bit RSA key to recover credit card numbers which is an acheivement worth much more than a few million credit card numbers!
Your suggestion for a token passing system is good, but fails my paranoia test since the CC processing machine does need to be internet connected. It is do-able with careful firewall design and if 1) or 2) wasn't acceptable then its the scheme I'd go for.
When I had to make this choice I chose option 1) - I really didn't think the company could stand the potential liability of hundreds of thousands of credit cards being exposed to the internet. Every time I hear of a database of credit cards being ripped off I'm sure I made the right choice ;-)