espressione regolare

[HenryXIII]

Prova così:

$stringa = "paolo-_-mario-_-giuliano-_-ida";

// togliamo 'paolo-_-'
$posiz = strpos($string, "-_-");
$stringa = str_replace(substr($stringa,0,($posiz+3)), "", $stringa);

// togliamo 'mario-_-'
$posiz = strpos($string, "-_-");
$stringa = str_replace(substr($stringa,0,($posiz+3)), "", $stringa);

// togliamo '-_-ida'
$posiz = strpos($string, "-_-");
$stringa = str_replace(substr($stringa,-(strlen($stringa)-$posiz)), "", $stringa); 

Non ho controllato il codice, perciò non ti assicuro il funzionamento. Cmq dovrebbe essere una cosa del genere.

Al massimo potresti raggruppare i primi due pezzi in un ciclo.