I added a line to the ZIP5 part of the LOT file to accept [A-Z][0-9][A-Z] as a format for ZIP. That did the trick, though it was clearly a hack.
Why is this not more clearly documented? I looked at ESRI Canada's web site and did not find a LOT file for download that would work with FSAs. Why?
What style locator rules are used in the 10.0 Street data that shipped with ArcGIS? I could see the reference data from the locator properties but could not identify the rules files. Was it a 10x locator?