I have been at pains to make all references to the site (both internal and external) the www version
Ouch! Now I really feel your pain.
This is a very disturbing report to me, especially because it sounds like you followed the direct advice that Google has given us about avoiding canonical issues -- advice that has worked for many websites. I can't quite fathom, given all that you did, why the site was indexed without-www in the first place.