Before I add my two cents here I'll mention that this post is rather old to be unanswered. If you figured this out already write an answer and choose it as "the answer" so it doesn't show up as unanswered and others can learn from it.
So, by "play" you could mean front to back (as in the length of the post/bolt) or around the bushing (as in a difference in the diameter of the post and hole in the brake arm).
I just checked the oldest canti-brake bike I've got (from the 1980s) and there is no play in either sense described above. So I would attempt to solve that problem next as the things you've already tried are all good, especially your choice of pads. You might want to try the salmon colored rather than the dual compound though. They are the better of the two compounds for braking but they wear out faster.
If it is the former type of play I agree with the advice of @Daniel R Hicks. If it is the other and you don't have replaceable canti-studs you ought to replace the brakes (arms) themselves. If there is play when they are at rest they will shimmy and shudder when braking. If there is play due to the strength of fork then you need a brake booster as suggested by @armb.
Another question for you - are both the brakes and levers original to the bike or have you replaced either? Mixing canti and v-brake components will cause problems but I haven't heard of noise being one of them.
A final note - take heart! I have a friend who is a fanatic about bike maintenance. He was a bike mechanic, but now is an engineer in aerospace and his bike stuff is rather high end. Last year he adjusted and replaced everything and never found the source of the noise. He replaced the bike instead!