Consulta a un campo de una tabla con criterios distintos

[superemir82]

Buenos días gente.
Tengo el siguiente dilema, que ni siquiera supe especificar describir en el título el problema.
Necesito filtrar una tabla de mysql con php la cual tiene id de países e id de paquetes de viajes, ya que un paquete de viaje puede visitar varios países. O sea es una relación de muchos a muchos. En la tabla pueden haber varios registros que tengan el mismo id de paquete pero tengan distintos id de países. Espero que me entiendan esta parte.
[b]Ahora lo que nesecito es filtrar con php y mysql los paquetes de viaje que incluyan distintos países que se seleccionarán en un select de múltiple selección. O sea ej. Quiero que me muestre los paquetes que pasan por Francia, Alemania y España (pueden ser más o menos los seleccionados)
No me sirve ni el OR o el IN ya que tiene que incluir todos los paises que se seleccionen, no uno u otro.
Con el AND lógicamente fue lo que primero que probé pero también lógicamente después me di cuenta que si filtraba primero ej. con idPais = 12 y hacia AND idPais = 20 , el resultado siempre va a ser 0 porque después de filtrar por el primero no quedan registros con id diferente a ese.
Espero me entiendan el problema y si es una tontería sepan disculparme es que el cuagulo no me deja pensar a veces.
Desde ya muchas gracias!!!!