- Invoke Control Panel from Start menu, then go to Add/Remove Programs
- Click on Add WIndows Components on the left. That gives you a dialog with Fax Services check box.
- Tick the box by clicking it, and press Next. This should install the files necessary for fax services, and may ask for the Windows XP CD.
The link I need to thank for identifying this fix: http://www.pcreview.co.uk/forums/thread-554812.php
Once I applied this fix, the fax services was installed. It also asked for the Microsoft Office software CD, but that went smooth, so finally the fax services started working (we never sent the fax after all this, but that was for another reason).
I was amazed and frustrated that something like this would require a complex unrelated security fix such as above. Let's just be happy other devices like TV, phones, DVD players are not as complex as a PC or Windows XP.