En tu descripcion tienes todos los datos necesarios para realizar la consulta. SImplemente debes excluir a los que aparecen en la tabla que mencionas en esta parte:
Cita: En la tabla solicitudes por su parte esta un registro por cada solicitud que se halla enviado al anuncio, los campos de esta tabla son: idSolicitud, idAnuncio, idPersona, idEmpresa, estadoPersona, estadoEmpresa... El campo idPersona es FK con la tabla personas y el campo idEmpresa es FK con la tabla empresas.
¿Cual es la duda? ¿Como escribirías TU esa consulta de exclusión de ese conjunto?
Desde ya no parece compleja... Consultas de exclusion pueden encontrar en casi todos los manuales y tutoriales.
¿Probaste hacerla?