I’m not a professional pilot but here is my $0.02. Just look at the regional’s job postings. Most, if not all, demand that you are able to enter Canada in their wording. Hell here is some of that wording on OO’s website:

“No pilot who has been convicted of any criminal offense that will prohibit him/her of gaining Canadian clearance will be hired to fly.”

MQ’s requirement:

“Ability to travel into and out of the U.S. and to all cities/countries served by Envoy”

After about five years you can apply for “rehabilitation” via the Canadian Consulate General’s office. You can apply at any time but >5yrs has the most success. I would have the waiver IN HAND prior to applying for any pilot job that has the requirements.