On the general question I asked — theorbtwo had a wonderful suggestion that lets me completely avoid having to deal with encryption at all. If I had to use encrypted data then I wouldn't be able to cycle through keys at will since other people would be holding the encrypted data. The best comprimise might be to use new keys for new data and switch as the opportunity arised.
If you're curious, theorbtwo suggested that I store all the data myself and only pass out tokens which reference the stored data. To do this, I'd store a key, an incrementing counter and then publish counter values and the Digest::SHA1 value of counter+secret. This also lets me change the key at will since all I have to do is store the expected counter and hash. Since random data is precious I have no idea how often I'd get a new secret but its also overkill for this application.
Now, mattr. This whole credit card deal is a tricky business. My first suggestion to you is to subscribe to the secprog list on securityfocus.com. You are about to step right from the deep-end of the swimming pool into the Atlantic ocean. You are going to need to be well armed when you go back to your client and change the requirements (what you've described so far requires an unsecure configuration). Read the archive and especially read the entire thread named "PGP Scripting". It sounds like that person's problem somewhat parallels yours.
Now here's my inexpert analysis (but augmented by what I've learned from being on that list). You cannot allow the server to decrypt the data. Ever. The key ideas to follow here are obfuscation and barriers. You're installing a level of obfuscation by doing things that might make the job technically more difficult but will not stop a determined attacker (oh yes, you must also write up an attack summary). This includes any use of encryption on the server where an attacker can decrypt your data.
The other level: a barrier is where you need to get to. The difficulty is that this is difficult. In general, your best bet is to use some form of encryption on the unsecure server, send the data elsewhere and on unrelated networks, only then can you decrypt the data and it never goes back to the front-facing server. This of course, implies that your application can never deliver plaintext card data. Your user cannot enter a password to get the data. That's just bad design. What you might do is restrict access to the encrypted data and then have your user do the decryption.
I think your question is too important and too hairy to be addressed by me in a response thread to an unrelated question. Ask in a new SoPW question and ask on the secprog list. I'm suggesting both because while the secprog list will probably furnish better answers the perl folk here will benefit by whatever gems are mentioned in responses but since secprog is chock full of people whose job it is to think of these problems, it'll have superior answers, generally.
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>