Elke voorwaarde of moet in een andere array staan. Probeer dit:
$Mongo->Compagnies->find(
array(
'$or' => array(
array(
"Name" => $regex,
),
array(
"Service" => $regex,
),
array(
"Description" => $regex,
),
)
)
);