This probably ties with the evidence.

See when I first put the drive in my PC [a Dell L733r model], it came up as a 9MB so I qunlocked it using the "normal" utility for this and rebooted as per the instructions, and then the drive showed up as a 120GB unit in the BIOS settings.

Then when I exited the BIOS setup [which rebooted the PC], the drive went back to 9MB and has stayed there ever since.

I suspect that maybe the Dell's BIOS is writing stuff like SET MAX ADDRESS into the HPA or overlay features and this is being used forevermore.

So, the real problem could be the shonky Dell BIOS.
I have tried another machine, which is a different Dell PC and it reports the same problem [9MB].

The Dell BIOS is a little weird as it lets you switch the mode of the BIOS setting for the drive from "Auto" [the default] to "User" or some other settings, like ATAPI CDROM etc.
But the disk "size" field in the BIOS setting stays fixed at 9MB.
Previously (when drive was unlocked) it showed up correctly as 120GB [but still not changeable], so I suspect the BIOS has told the drive you're now 9MB in size and it believes it.

The Dells I am using are about 2.5 years old, so the BIOS'es are probably hopelessly out of date for these modern drives and OVerlay/HPA implementations.

I don't have a newer PC to try fiddling with this on. [or maybe an even older non-DELL might be worth a crack as it might unjam things].

Worst case, your utility program sounds like it will be useful to have around.
If I know the drive can probably be recovered ok, I will go buy another drive so I can get my Tivo on the air again, until you get some time to do the utility you mentioned if we still have the problem.

I can't believe that this is unique to Dell BIOSes though and I am wondering if there is not a flaw in the Firmware in the drive itself.

Tman - is your drive firmware the same as mine [see the above hdparm output info]

I may call the local Maxtor reseller I bought my drive from tomorrow to see if they know of this problem and if there is a fix for it.
The Maxtor website is not very useful for this sort of thing.