Bueno, lo de "a mano" seria algo asi:
Código PHP:
$resultado=array();
foreach ($vehiculos as $vehi) {
$esta=false;
foreach ($vehiculos2 as $vehi2) {
if ($vehi['matricula']==$vehi2['matricula'] && $vehi['aparcamiento']==$vehi2['aparcamiento']) {
$esta=true;
break;
}
}
if (!$esta) $resultado[]=$vehi;
}
echo '<pre>';
print_r($resultado);
echo '</pre>';
en lugar del array_diff().
Ojo, el codigo lo he puesto de cabeza. No lo he probado, pero la idea es esta: para cada valor del primer array, decorres el segundo array mirando si coincide con alguno de sus elementos; si no coincide con ninguno, lo añades al resultado.
Suerte.