Come ti è stato suggerito, il protocollo ICMP non ti serve in questo caso, e su questo fattore hai convenuto anche tu.

Per quanto riguarda il programma che devi realizzare, il protocollo più adatto dovresti sceglierlo in base al tipo di connessione che desideri instaurare. Mi spiego, se il colloquio tra i due PC è un "connessione+botta+risposta+disconnessione", mantenendo però il PC connesso al server per tutta la durata in cui esso deve essere considerato "online", allora il protocollo TCP è quello più indicato; se invece devi solamente inviare una notifica al server senza usufruire di uno stato di connessione permanente, allora ti basterebbe usare il protocollo UDP, molto più rapido in questo senso.

Approfondendo il lato tecnico, in Delphi puoi usare i componenti Indy per creare un client e un server appropriati e scambiare dati tramite socket.

I componenti sono presenti nelle più recenti distribuzioni di Delphi; in caso contrario, li trovi nel sito ufficiale.

In merito all'esecuzione in background, come desideri che si comporti esattamente il tuo programma? Fino a che punto vuoi nasconderlo? Partendo da un'applicazione comune dotata di un form principale, il massimo che puoi ottenere è un programma che sia visibile solamente come processo nel Task Manager, oltre non credo tu possa andare.

In quel caso, forse basterebbe creare un'applicazione Windows disabilitando la visualizzazione del form principale (Application.ShowMainForm impostata a False) e dando vita ad un ciclo che tenta di connettersi ad intervalli regolari, inviando in "PING", intercettando eventuali eccezioni (ad esempio, i timeout)...in sostanza, governando l'intero sistema che devi mettere in piedi.

Ciao!