This may not be your problem, but something to bear in mind:
There are many tales and anecdotes circulating about odd start up behaviour when using the MAX7219/21, for example: [SOLVED] pull-up or pull-down resistor on LOAD of MAX7219 - LEDs and Multiplexing - Arduino Forum . Possibly, certain MAX clones have contributed to this by having their own unpredictable behaviour.
I have has some recent success with a 10k pull up resistor on the LOAD (CS) pin, having suddenly started seeing such problems in an old, and previously working, installation. And that, despite doing an initialisation of the MAX chips in the setup() routine.
Anyway, it could also be a coding problem or, as has been suggested, a wiring error.
Post also the code you are using.