I should point out that it does depend on the specialty. Currently, *most* specialties are cross-eligible for the board certification exam. For example, a Canadian IM, Rads, Derm, Path, Plastics, Gsurg, Uro, OBGYN etc. is eligble for the US specialty exam, and the US resident is generally eligible for the Canadian FRCPSC exam. This issue is independent of immigration/visas which usually is handled by the employer at that stage of the game.
US: State License (USMLEs) + BCertification + Visa = golden
Canada: MCC Exams + FRCPSC certification + Visa = golden
However, notable exceptions are Cardac Surgery (a direct entry program in Canada), Neurosurgery and Otolaryngology H&NSurg. For various reasons (apparently mostly physician oversupply in the US), these Canadian residents are not US eligible (not sure about going the other way either). So these people can basically only work in Canada or in academic practice in the US where BC/BE is not as crucial.
Anecdotally, I have heard and seen first hand that it is relatively easy for Canadian trained physicians to move to the US. This "brain drain" is a hot topic in Canada. Apparently, however, recently some MDs have moved up here because of the nicer malpractice situation. It cuts both ways I guess.