Ciascuna o condizione dovrebbe trovarsi in una matrice diversa. Prova questo:
$Mongo->Compagnies->find(
array(
'$or' => array(
array(
"Name" => $regex,
),
array(
"Service" => $regex,
),
array(
"Description" => $regex,
),
)
)
);