In reply to duzinga: Thanks for all the responses and suggestions everybody. Yes the climbing wall in question is in Japan, so HSE can not help (Hi Rob!).
I went down to the wall and talked to some of the guys, and they told me they checked behind the wall to see what's wrong with the bolts and they think it's safe to use these bolts. Here is what they found:
Just like Fraser said, there is a thick structure immediately behind the ply through which the bolts pass. From what I understand these "structures" are wooden blocks but I am not sure (communication problem!). The students I talked to tried tightening/loosening the bolts as a pair (one behind, the other in front of the wall) but they said it was stuck and seemed impossible to loosen/tighten. From their observation, the reason for the spinning bolts are a "slight damage" on the ply, which created a gap hence allowing the bolt to turn freely.