I've noticed this too in XP. I have no problems at all w/ autocomplete in NT4.0. Also, autocomplete will not work in some fields that are designated not to allow autocomplete (ie: confirmation fields)
One thing that will disrupt autocomplete is programs like WindowWasher, if you don't deselect the correct options, it will delete this info and obviously autocomplete will not have the stored info to complete anything.