Don't think for a minute it's only AmEx...
My UK bank, who for the moment shall remain nameless, presented me with a predictable replacement card number which the original scammers tried to predict in a subsequent phishing e-mail.
All the bank did was increment the second-to-last digit and recompute the final Luhn check digit. Turns out that most card numbers are in the format AAAA BBBB BBBB BBCD where A is the issuing bank's range, B is the card account number, C is the (sequential) issue of the card and D is the check digit; i.e. the only thing that changed between cards was digit C being incremented.
Very, very uninspiring. Went into a bank branch with a pad and a pen to explain this to them and ended up on a videoconference to someone somewhere. End result was a completely new card number being issued, but it took a lot of shouting to get that done...