Do I understand correctly that the grid is rotated relative to the sides of your box? I.e. the intervals of the grid lines interjecting the bounding box are not constant?
In this case some labels get omitted if there is not enough space for them. So far I haven't found a solution to force ArcMap to display all the labels. You could either try to shift your map a little bit (it that is an option) to change the intervals and get all labels to display. Or convert the grid to graphics and place the labels manually (or just add any missing label as text). Obviously then you loose the link to your map, so shifting your map after the conversion will not shift the grid...
Not a real solution, I know, but maybe it helps anyway. Cheers,
Kathi