Get on a land line or another cell phone that is not the one that you are having the problems with and call Verizon Tech support. Tell them at the Tier 1 level that you have done all the trouble shooting steps that they would normally do and ask for a Tier 2 tech. Once you get that far, tell them the same thing. They will access your phone and see what's going on. The worst case scenario is that they will give you another MAXX. I would advise against it only because I went thru 2 Bionics and they switched me to the MAXX. Get the MAXX HD or something.
I'm still working on their Tier 2 tech side to get up to the MAXX HD mostly because of the lack of accessories that are offered online at Verizon or in the store. But I also don't want to go thru 2 or 3 MAXX phones. I'm having lag issues with mine and no matter what I do, safe mode, FDR, soft reset, nothing works to get rid of the lag totally. I love this phone but I just want it to work right without having to root it.
In the end just call Verizon and have them do what they do to try and fix it. The random reboot to me sounds like a reason to bump you to a different phone.