I had a lot of problems with m0n0wall when I was using an older machine. It just didn't seem to like the hardware in the machine! Sometimes it would shut down because of a power outage... but then it would not boot back up all the way. Like it would just pause in the middle of booting up. I would usually end up switching to a beta version, re-burning the CD (I used the bootable cd back then), formatting a new floppy, etc.. just to get it running again because that's all that seemed to work. And then I would have to re-do all my settings. Too much of a hassle to get it working again.
Even 1 time I had a huge problem with the mac spoofing. I would change the MAC address on my WAN interface through m0n0wall, and the internet would cut out (even though spoofing worked fine on my linksys) and not come back even if I cleared the spoofed mac. I had to clear out the spoofed mac AND reboot to get it working again. Sometimes, even re-doing all my settings.
But since then I've switched machines completely to newer hardware, network cards and all, and I have never had these problems! And nowadays I am using the generic-pc version (on a hard drive instead of a bootable cd). Much faster, and works great. Don't know why I was using the bootable cd/floppy combo before... I was just too lazy to read how to get the hard drive working.
Anyways sorry to go off, but basically when I had these problems it was definitely hardware related (probably the network cards), and switching to a newer machine has been great. If you have an another old machine laying around you could try it, but my guess would be incompatible hardware, or just old/quirky hardware. Sorry I cant give a definitive answer