I have seen this problem and all the solutions listed are for Vista and Windows 7. These won't work on XP though. What finally did after I got rid of the virus that caused this by using combofix and malwarebytes was to copy the sharedaccess reg key from a know good machine and replace the one on the bad machine.
Here is the key:
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess]
"DependOnGroup"=hex(7):00,00
"DependOnService"=hex(7):4e,00,65,00,74,00,6d,00,61,00,6e,00,00,00,57,00,69,00,\
6e,00,4d,00,67,00,6d,00,74,00,00,00,00,00
"Description"="Provides network address translation, addressing, name resolution and/or intrusion prevention services for a home or small office network."
"DisplayName"="Windows Firewall/Internet Connection Sharing (ICS)"
"ErrorControl"=dword:00000001
"ImagePath"=hex(2):25,00,53,00,79,00,73,00,74,00,65,00,6d,00,52,00,6f,00,6f,00,\
74,00,25,00,5c,00,73,00,79,00,73,00,74,00,65,00,6d,00,33,00,32,00,5c,00,73,\
00,76,00,63,00,68,00,6f,00,73,00,74,00,2e,00,65,00,78,00,65,00,20,00,2d,00,\
6b,00,20,00,6e,00,65,00,74,00,73,00,76,00,63,00,73,00,00,00
"ObjectName"="LocalSystem"
"Start"=dword:00000002
"Type"=dword:00000020
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Epoch]
"Epoch"=dword:000006ad
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters]
"ServiceDll"=hex(2):25,00,53,00,79,00,73,00,74,00,65,00,6d,00,52,00,6f,00,6f,\
00,74,00,25,00,5c,00,53,00,79,00,73,00,74,00,65,00,6d,00,33,00,32,00,5c,00,\
69,00,70,00,6e,00,61,00,74,00,68,00,6c,00,70,00,2e,00,64,00,6c,00,6c,00,00,\
00
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy]
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\DomainProfile]
"EnableFirewall"=dword:00000000
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\DomainProfile\AuthorizedApplications]
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\DomainProfile\AuthorizedApplications\List]
"%windir%\\system32\\sessmgr.exe"="%windir%\\system32\\sessmgr.exe:*:enabled
xpsp2res.dll,-22019"
"%windir%\\Network Diagnostic\\xpnetdiag.exe"="%windir%\\Network Diagnostic\\xpnetdiag.exe:*:Enabled
xpsp3res.dll,-20000"
"C:\\Program Files\\Microsoft Office\\Office12\\OUTLOOK.EXE"="C:\\Program Files\\Microsoft Office\\Office12\\OUTLOOK.EXE:*:Enabled:Microsoft Office Outlook"
"C:\\Program Files\\Microsoft Office Communicator\\communicator.exe"="C:\\Program Files\\Microsoft Office Communicator\\communicator.exe:*:Enabled:Communicator"
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\DomainProfile\GloballyOpenPorts]
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\DomainProfile\GloballyOpenPorts\List]
"3389:TCP"="3389:TCP:*:Enabled
xpsp2res.dll,-22009"
"1900:UDP"="1900:UDP:LocalSubNet:Enabled
xpsp2res.dll,-22007"
"2869:TCP"="2869:TCP:LocalSubNet:Enabled
xpsp2res.dll,-22008"
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\StandardProfile]
"EnableFirewall"=dword:00000001
"DoNotAllowExceptions"=dword:00000000
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\StandardProfile\AuthorizedApplications]
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\StandardProfile\AuthorizedApplications\List]
"%windir%\\system32\\sessmgr.exe"="%windir%\\system32\\sessmgr.exe:*:enabled
xpsp2res.dll,-22019"
"%windir%\\Network Diagnostic\\xpnetdiag.exe"="%windir%\\Network Diagnostic\\xpnetdiag.exe:*:Enabled
xpsp3res.dll,-20000"
"C:\\Program Files\\Microsoft Office Communicator\\communicator.exe"="C:\\Program Files\\Microsoft Office Communicator\\communicator.exe:*:Enabled:Microsoft Office Communicator 2007"
"C:\\Program Files\\Microsoft Office\\Office12\\OUTLOOK.EXE"="C:\\Program Files\\Microsoft Office\\Office12\\OUTLOOK.EXE:*:Enabled:Microsoft Office Outlook"
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\StandardProfile\GloballyOpenPorts]
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\StandardProfile\GloballyOpenPorts\List]
"3389:TCP"="3389:TCP:*:Enabled
xpsp2res.dll,-22009"
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Setup]
"ServiceUpgrade"=dword:00000001
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Enum]
"0"="Root\\LEGACY_SHAREDACCESS\\0000"
"Count"=dword:00000001
"NextInstance"=dword:00000001