We used to bring a Sharpie. We write our cell phone number on the arm of each child. (Now my kids have Mom and Dad's cell phone numbers memorized - and know which hotel we stay at and all the rest).
We tried tags - lost after the first day. That was when we discovered the ball point pen in the hotel room could be used - and subsquently refined it with the Sharpie.
This is what we did too. We used to put a paper in their pockets, cut this method worked for us...and we never needed it. I think the tattoo idea is great too!
