Ciao,
la precedente indicazione di kungfu credo possa aiutarti. In ogni caso, metterei su du piani differenti la gestione dei 404 e dei 301. I 404 vanno gestiti comunque in odo tale da non perdere traffico acquisito nel tempo.
Nel tuo caso, credo possa aiutare una pagina 404 ben strutturata o, in alternativa, il rimando alle categorie (se presenti).
Come tu fai notare "Le pagine più vicine tematicamente potrebbero essere le schede degli hotel ai quali si riferivano dove ci potranno essere pacchetti oppure no". Questo significa perdere potenziali clienti con un redirect verso pagine che poi non interessano.
A ben vedere, visto che alcuni hotel includono dei pacchetti, nella 404 puoi eevidenziare quelli che hanno questa specifica invitano poi il navigatore a cercarne altri simili.
Un A/B test aiuterebbe molto per capire che decisione prendere.