[SYWARE]

Cuando cerramos el programa de forma manual, el icono sí que desaparece.
Está claro que el programa se está encargando de eliminarlo del systray.
Para eliminarlo con el shell_notifyIcon precisaría conocer los parámetros para eliminarlo, especialmente el handle.

Código Delphi [-]
 
Procedure TForm1.QuitarIconos;
var 
  Info: TNotifyIconData;
begin
  Info.cbSize := SizeOf(Info);
  Info.Wnd    := Handle;
  Info.uID    := 1;
  Shell_NotifyIcon(NIM_DELETE,@Info);
End;

Si hubiese una manera de recorrerse todos los tray icon del systray e irlos comprobando por su nombre y obtener el handle para poder eliminarlo, estaría bien, pero seguramente hay algún método más sencillo.