[roman]

De hecho la pregunta es ambigua. Una cosa es el explore.exe como shell y otra como manejador de archivos aunque sea el mismo ejecutable.

Suponiendo que se refiere al primer caso, ciertamente se ejecuta al inicio,(salvo que configuremos el sistema de otra manera) y cada vez que hay que reiniciarlo por algún fallo, como indica jachguate.

Siempre que se inicia como shell, el explorer manda el mensaje TaskBarCreated a todas las ventanas (propiamente lo manda cuando crea la barra de tareas pero es casi lo mismo) así que sólo hay que captar este mensaje.

Pero hay una complicación. Este mensaje no es como los WM_XXX que podemos interceptar con un simple

Código Delphi [-]
type
  TForm1 = class(TForm)
  private
    procedure WMXXX(var Msg: TMessage); message WM_XXX;
  end;

porque TaskBarCreated no es una constante numérica.

Para poder detectarlo debemos hacer dos cosas:

1. Registrar el mensaje al iniciar la aplicación:

Código Delphi [-]
CMTaskBarCreated := RegisterWindowsMessage('TaskbarCreated');

donde CMTaskBarCreated es una variable de tipo Cardinal.

2. Reemplazar el procedimiento de ventana del formulario principal:

Código Delphi [-]
  TForm1 = class(TForm)
  protected
    procedure WndProc(var Msg: TMessage); override;
  end;

implementation

procedure TForm1.WndProc(var Msg: TMessage);
begin
  inherited;

  if Msg.Msg = CMTaskbarCreated then
    (*
        Hacer lo que haya que hacer
    *) 
end;

// Saludos