You are accepting payments on behalf of other merchants (those offering travel experiences) and that brings risk. Unfortunately this is not an issue limited only to Paypal, many other payment operators will reject you for the same reason; the fraud liability is just all over the place with such systems and they won't want to take the risk.
It sucks, but there you go.
If you are really looking at 10's of Millions in revenue over the next few years.... go to your bank and work something out with them, although it might be initially expensive while the offset the risk.