The Maxtor (zero-fill) utility is generally OK for most current make of drives. Zero-fill is often mistakenly referred to a low-level format util (LLF); it is in fact more correctly a mid-level format util (MLF). A true LLF would wreck a current drive, so don't use one of those... MLF setsdrive back to as close to factory-gate state as you can achieve... Afterwards start afresh configuring/formatting the drive.
If you look on the drive casing there should be a model number... (perhaps even manufacturers code). Google with that and you may find what make it is?
As regards the innaccessible boot-drive message: it can be down a few items. Typically it can be flakey/incorrect driver. Worse case - failing drive...; but that would be low on my list - initially...
http://labmice.techtarget.com/troubleshooting/errorcodes.htm
and scroll down quite a ways... There is list of assorted causes etc.
re' the never ending format...
Use '98 Fdisk and delete all partitions; then reconfigure afresh and then either allow W2K CD to reformat it during setup (as fat32/ntfs - your choice but be aware of the W2K issue with fat32 and formatting partitions over 32Gig); or use '98 to preformat as fat32 (and it can be in excess of 32gig); and if you want ntfs then use W2K setup to reformat during that sequence.
Incidentally - how big is this drive? W2K cannot create a partition in excess of 32Gig as fat32; to go larger (as fat32) you use a '98 bootdisk (format util). It can however create/format one as ntfs in exces of 32gig.
Long shots; RAM may also be an issue...
Do you have the correct driver(s) for W2K on this laptop?
Note that all members of the NT strain (NT thru to W2K3 and Longhorn...) all present you with a boot-menu when you boot up. It can be disabled/bypassed by setting time to boot to default OS to zero and thus you boot straight thru' to the default (only?) OS.
If you had XP as an option there too, it would/should have been a simple matter to edit out references to XP from the boot.ini.
I have seen some less than enthusiastic comments about NAV2005 per assorted OS... Possibly you have been "blessed" with some of those apparent irriations too... I would tend to avoid NAV these days and use one of the various freebies out there.
AVG is OK for many folks. (However I had problems with it on an ME installation - screwed up dial-up access to the www; removed AVG and all was well.) Some like Fprot, some Pandasoft. I find Avast (avast.com) works without any problems (on both ME and W2K systems where I've installed it); easy to use and it's very low on resources etc. Auto-updates definitions like a dream...