Something like "DL1234" and "DZ1234" for Delta?
I know a lot of the two-letter codes are claimed too, and I'm sure there must be some reason this wouldn't work OK, but it would seem like they they would each have at least one code left over from the various airlines they've acquired over the years?
If an American Airlines regional flight started with "TW1234" again, for example, I don't think it would break the world.