Ouch.
First, try a regular factory reset now that you have done the formatting-reset to see if they will connect to the network at least.
Second, do you have a phone console cable that you can look at the CLI of the phone? It's been so long I don't know if I still have the pinout to build one, but the Internet never forgets....
Third, not telling you anything you don't already know but it might be time to upgrade the phones....
Maren
