I know everyone here favors the Domain Dance, then a format/reload, but I have seen NT 4 migrations go smoothly over to 2000 without that hassle (On the scale of thousands of servers). The biggest problem is incompatible software or drivers. Depending on your server, there may be a utility you can run to prep it for an upgrade. Compaq for example released this primer that would strip out trouble causing components before the upgrade.

Best thing to do if you plan on going this route is have at least TWO verified backups before even touching the origional server. If you have the spare equipment, try it out. In general, quite a bit of effort is put into the upgrade tools for servers.