Ouch, reformatting seems a bit drastic.
We're using Windows Server 2003 since it's release and we haven't had any issues. Maximizer support has published an KB article (not the one above) for configuring step-by-step the installation on a network. A search should pull it up.
The article referred to by the previous poster may have some validity but then I imagine you've check out your network connectivity.
DHCP hasn't presented us with any problems.
The only thing outside of following Maximizer's procedure for installing on a network that affected our connectivity was brown outs. We would experience brown-outs of less than 3 sec. duration that would affect the server more than the workstations it seemed but that was an easy fix - b/u power supplies.
On another note, you mention your using Max 7 with Service Release 3 - there's only been two service releases for Maximizer. Enterprise has had three - which one is it?
Certainly, there's more things one could check but then you'll have to provide more details.
IRIS