This is the first thing I did:
Start -> Control Panel -> Sound and Audio Devices -> (tick) Place volume icon on taskbar
... and click OK.
The above is a recommendation from Microsoft KB279435.
Performing the above did not seem to work. So I dumped his registry and compared it to mine. For this kind of problem, check this registry key:
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Drivers32]
"wavemapper"="msacm32.drv"
Add wavemapper as REG_SZ (String Value) with value "msacm32.drv".
Logout and log back in. If this does not restore the volume icon, run "systray.exe".
Start --> Run.. --> systray.exe
Addition of the above registry key restored the volume icon on the system tray.