I agree that, in principle, you should not be offered the patch if you already have it installed. However, MS Update is not foolproof and errors do happen.
Is the patch in your Add/Remove list?. If it is, you have to decide whether to believe Add/Remove or the update prompt. You could also run the Secunia Software Inspector which should pinpoint if any important patches are missing;
http://secunia.com/software_inspector/ (This requires an up to date version of Sun Java to be installed on your computer. If you're not sure if you have it, or which version, you can use the java tester here;
http://www.javatester.org/).
If the SSI confirms that the patch is missing you could try going to Windows Update to use the 'Custom' option to collect the patch that way. I've never used Automatic Updates so I don't know if you might have to disable it in order to use the Custom option.
When I used '98, I frequently got updates from the Catalog site. These came as .exe files which could be d/l and doubleclicked on to install. This worked as long as you knew exactly which patch you needed. I don't know if it works for XP but will do some research.