In the end we did not do a login message. We have Expense as well as Travel and we didn't want to hit Expense users with the message as it's specific to Travel. I wish there was a generic ... when you click a travel search message (and yes, I know I can do an air search, hotel search, car search but I find that a little clunky as they could see duplicate messaging). In the end we decided to add an "Important Notice" banner to the top of everyone's Company Notice then we also added a custom field (at start of booking) to have them stop and select this is an essential business trip. It's also a little clunky but I thought it would stop and give them a brief moment to think first before continuing.