arcgis 10.0 - Very Inaccurate Geocodes in Canada (Quebec)

Edit: Found this page detailing the standard geocoding abbreviation types which may be of use when trying to match foreign street types. It appears that we'll have to create a much more robust version.

The problem is as listed in the title: Our current geocoding attempts (using a proprietary list of addressed and a proprietary streets network) in Quebec are coming up with abysmal match rates (40-50% overall). We have tried looking at problems with characters sets and postal code inconsistencies, but nothing seems to be nailing it down. Presuming these two factors are not the issue, what suggestions might be offered as possible pitfalls when geocoding in this area?

Important notes:

1. Geocoding with ArcGIS 10

2. Using FSALDUs as post code in "ABC XYZ" format.

Here are some example addresses.

    ARC_Street          ARC_ZIP     CITY                           STATE
1134 BRIDGE ST W        A7R 3L1     NAPANEE                         ON
75 RUE PRINCIPALE       G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC
43 RUE PRINCIPALE       G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC
325 RANG SAINT-JACQUES  G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC

325 SAINT-JACQUES RANG  G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC
125 RUE PRINCIPALE      G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC
168 RANG SAINTE-ANNE N  G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC
168 RANG SAINTE-ANNE    G0A 1A0     SAINTE-CHRISTINE-D'AUVERGNE     QC