Yep, I encountered the problem too, so did a check of how they are evaluating the entry and found this expression test:
="^[A-Za-z][\d][A-Za-z][ ][\d][A-Za-z][\d]$"
What that boils down to is a simple pattern check to see if the 1st digit is alpha, followed by number followed by alpha folowed by SPACE followed by number...alpha...number.
So, I checked Montreal's City Hall at h2y 1c6 and it PASSED! It also passed with UPPER CASE alphas.
Use a blank between the the first three and last three digits, which is the standard (from my days of Canada shipments).
Try that... Danno