I can help with this.
You have a site thats travel related - that sector has hot keywords, its very very competetive. Our own websites are also in hot keyword related sectors so we can give you our own thoughts on your problem. The same rules dont apply to other search term areas imo
From my own experience in these areas even sites out of the sandbox still get restricted in some way for some time. it looks like (again own experience) that google applies some weight to the value of the page rank in relation to how often it spiders the page, how deep it will go and how much value it gives it in the serps. With a low PR index page, google is going to almost discount the value of your content no matter how good it is!
For example, one site that is PR7 and has PR5 internal pages has very little issue with a) being spidered on a regular basis and b) pages 2 deep being indexed and none of the pages are supplemental.
Meanwhile three another sites thats are PR4/PR5 that are in similar
areas, full of rich unique content but are less than one year old, suffer from supplemental issues for some pages or simply have ranking issues. ie they should feature in the serps for certain keywords yet they dont due to the sandbox effect and or other filters that they now apply.
We have had site pages returned out of supplemental hell, by increasing site content and internal links. Please note that even pages not classed as supplemental can sometimes have the same ranking problem due to these filters. For example you may find the page listed after other supplemental pages for an abscure search term so even if the page isnt stamped supplemental, its as good as!
The issue you face whilst it may have be to do with very similar pages is more likely to be as a direct result of additional filters restricting you due to the sector you are in.
The cure to your problem imo is to get many more inbound links (some authority ones if possible from related sites) to internal pages as well as to your index page. You should find pages start advancing in the future - its going to take time.
If i was working in your sector, currently based on the filters recently introduced i would be working on at least a 18mth-2yr time frame, before i would expect to rank for anything meaningfull, you might be lucky but i think its purely down to the keyword and how much demand there is for adwords for it.