I would immediately contact Adobe. They will have a record of your purchases. Up to a certain time, they offer replacement discs for a nominal fee. Since CS4 has been shipping for some months, I would hurry. If they still offer this for CS3, it will probably not be for long.
i think, there should be a time after you launch a new product (CS4) you have to give service and "spare parts" for older versions. we updated from Cs to Cs3, and want to wait awhile. CS4 came too fast, we just purchased the cs3 several months ago. is there anywhere on the adobe site it can be downloaded?