No el lugar no es el problema, mientras este despues del codigo para que se pueda ejecutar la condicion esta bien..
proba con:
Código PHP:
if( empty($sexo) || empty($interestin) || empty($pais) || empty($estadocivil)){
echo "No se han encontrado resultados";
}else{
echo 'otra cosa';
}
ahi te daras cuenta si es que esta mal hecha la condicion.. puede ser ese el error.
Saludos,