It sounds to me like the zipcodes need to be recorded as text rather than numbers, or else you'll lose your initial zero. What are you trying to view the contacts in? Outlook itself shouldn't drop the 0, but if you are viewing them in Excel, it will consider the zero's as part of a whole number and drop them. Then you just format the zip code cells to be text rather than number.
It's Outlook dropping the 0! Maybe it's cos I imported the contacts, but even after I went in and edited the 0 still won't stick.