The issue of credentials recognition is exceptionally complicated, partly because of the different standards of training in different areas of the world and partly because for many professions governments actually don't issue credentials. They're part of trade and professional associations, and governments require these credentials, so the stakeholders involved are beyond governments.
I would say that the federal government probably has a role to play--and I think this is an excellent question, by the way--in perhaps convening some sort of a body made up of representatives from municipal governments, provincial governments, the federal government itself, and stakeholders to deal with this issue and perhaps to deal with some of the other issues I've raised. That would be my suggestion for what could be done.