In my current job, I have only had to do a team building exercise once, but it was great. We were divided into teams and handed boxes of small jigsaw puzzles and told to assemble them.
After 2 minutes, someone came around and took away the cover with the finished picture on it ("Building blueprints have been recalled for modifications"). Then another 2 minutes, and each team was handed a pair of heavy work gloves and informed that one member had to wear them ("New federal safety regulations"). Then "budget cutbacks": someone took away some of our pieces.
The whole point was that this is a metaphor for government work (I'm in Civil Service), and the important thing is to maintain a sense of humor, be creative, and keep on working with each other. My team got applauded because the member who wore the gloves, wore them on her head.
Another exercise was to recount one of the best experiences you had ever had while working for the department, and that was fun too.
It also helped that TPTB took us all out to lunch afterward, and told us we were a great team. And that was probably the whole point: we appreciate you and you're a great team.