One suggestion would be to use the "Login Warning" under Travel Admin > Custom Text>Login Warning.

This will display whenver the user logs in so it doesn't matter what they search they will alway see the message when they login and not multiple times when searching with air, car, and hotel search messages.