Ok, I'm not a cryptographer, so I might be missing something here big time.
But the whole PSN-disaster (I'm a customer) made me think: there is good reason to store credit card information, like the PSN did. Because, frankly, I'd be annoyed to enter a 16 digit number each time I buy some 10 buck game.
But why can't SONY (and anybody else who works with credit-cards) just encrypt them with a public key they agreed on with the CC-company, and only they can decrypt it? So if there was a security breach, we just revoke the key, and are done with it? Is that too simple?
With it stored on your gateway's servers, they will usually provide an API that you can use to issue transactions against the stored user data (it shouldn't return the CC data, just run transactions against it).
I'm heavily against storing CC data on my own servers - I store the last 4 digits (for display purposes to users) but that is it.