hmmm, very strange. I just tried it with zipcodes entered as text format, zipcode format, and a bunch of other different ways and in every case, it exported it out with the leading 0 in place. (I'm using Excel 2003 as well). There must be something very strange in the way the data was either first entered and then reformatted or something.
Suggestion #1: copy your column of zipcodes and then do a paste special > Values into a blank column. Format that column back Text format. Then copy/paste it back to your original data. This helps force excel to set all the data to a text format.
Suggestion #2: not an elegant solution but if this is a "one-time" export, change all zipcodes to include some "special" character that doesn't appear anywhere else. Then export it, open the file in something like Notepad and do a search/replace and remove all the special characters. For example, in some blank column enter
="@@@"&A1 (where A1 is whereever your zipcode is). This will turn your zipcode into something like "@@@01234". Then copy/paste special, Values back ontop of your original data and delete the formulas. After you've exported it to CSV format, open it in Notepad and do a find/replace for finding @@@ and replacing with a blank.
I know it's not the most elegant solution, especially if you're doing this export a lot but it would at least get you around the problem for now.