I am using 9.3 as well and this also appears to be the case when creating a MGRS grid using the Grids tab under the Data Frame Properties. If you are working with data less than 10000 meters from the UTM 0 northing (the equator) than the northing grid labels do not appear. The easting labels appear as usual.
If I go into the Grids tab, Label tab, hit the Additional Properties button, and then the Principal Digits button I can change the settings to make 1 digit of the northing label to appear. For example, if I'm at the 1000 m gridline I can change the number of principal digits to 1 and and the number of base digits to 3 then a '1' will appear as the label. There a couple problems with this. The first is that this approach changes the easting to show 3 digits (the first two being superscript). If that was the only issue I could make a 2nd grid to label the northings. However, my product's specifications requires 2 digits for the grid labels. I need to northing label to read '01'. Since in the coordinate system there is no 0 before the 1000 meters this doesn't seem possible using this method to create grids. However, I need my grid to be dynamic so as far as I'm aware this is my only option.
Any thoughts about this situation? Thanks in advance for any help that can be offered.