From a purely technical point of view, this is a very interesting question. The first thing that comes to mind is by far not an elegant solution, but maybe a working solution - open the Start Menu:
SendMessage(hAnyWnd, WM_SYSCOMMAND, SC_TASKLIST, 0)
I will see if I can find another solution.
(Well, the most obvious solution, of course, is to BringWindowToTop(hTaskBar), but that appears not to work.)
One way I'm looking at doing it now is by sending the escape key from my notifyicon app.
SendKeys.Send("{ESC}");
This works as the standard behaviour for a fullscreen app is usually to exit the fullscreen mode when escape is hit on the keyboard. I still don't think this is the best solution because there may be times when forcing an ESC might have side effects if the user is doing something else...but it may well be "just good enough"
How about the other solution?
Not to make the main application full-screen: it will cover the whole screen view except the area where the taskbar is always positioned by default. If the taskbar is repositioned to other side, the application will be notified by OS to refresh its window size, but it will always avoid the new taskbar area. The worst case is when the taskbar is set auto-hidden. It will not look so nice though.
If it's no problem that the start menu will popup than you could press the windows button.
keybd_event(VK_LWIN, 0, 0, 0);
keybd_event(VK_LWIN, 0, KEYEVENTF_KEYUP, 0);
Works fine for me under Windows 7.