Let's begin with a simple experiment that you can perform on your own computer:

1. Count the number of icons in your Taskbar Notification Area, including any rarely used icons that Windows XP may have hidden under the little blue less-than button. The Taskbar Notification Area is that part of your Windows taskbar near the clock where lots of little icons go. [1]
2. Kill explorer.exe. (If you're a command line type running Windows XP or later, “taskkill /im explorer.exe /f” will do the trick. If you're a GUI type, start Task Manager (Ctrl-Shift-Esc or your preferred method), choose explorer.exe and choose “End Process”.)
3. Restart explorer.exe. (From a command line: “explorer”. From TaskMan: File->New task... “explorer”.)
4. Once your taskbar is back, recount the number of icons in your notification area.

Chances are enormous that you have fewer notification icons than you started with. On my computer, the number went from 10 to 4! (Only Outlook, Windows Messenger, eTrust Anti-virus, and the Windows volume control survived. Lots of stuff didn't.)

Those icons will probably stay gone until you stop and restart the program responsible for each of them. Where did they go? Why did they go there?

It turns out that explorer.exe [2] loses all information about what icons were displayed there when it dies (and who can blame it for that?). It is up to each application that wishes to use the Taskbar Notification Area to remind explorer.exe's reincarnated self what it wanted displayed. The method by which your application properly gets notice of the reincarnation of explorer.exe (or, more specifically, the creation of the Taskbar) is described by MSDN Library as follows:

With Internet Explorer 4.0 and later, the Shell notifies applications that the taskbar has been created. When the taskbar is created, it registers a message with the TaskbarCreated string and then broadcasts this message to all top-level windows. When your taskbar application receives this message, it should assume that any taskbar icons it added have been removed and add them again. This feature generally applies only to services that are already running when the Shell begins execution. [Search for “Taskbar Creation Notification” at [3]]

This obscure little MSDN Library gem makes it sound like there's no reason a normal app should care about notification that the taskbar was just created, but as we just saw, real apps can be affected in a case where explorer.exe crashes or gets killed. While explorer crashes are not a terribly common occurrence in modern Windows releases, they are not unheard of. There is little reason not to get this behavior right considering that you can probably implement it by adding 6 or fewer lines to your window proc as shown in the example code in the above-linked MSDN Library article.

Excuse me while I restart so as to get back my other notification icons...

Footnotes
[1] You may know this as your “tray” or “systray” but Raymond Chen explains why you might think that, and why you would be wrong.
[2] The Windows process responsible for drawing much of the Windows desktop, including the taskbar.
[3] inline link to MSDN Library article