I figured it out (had to take a look at the smart_home.py code in HA).
It has to figure out how to categorize a sensor (for Alexa) as CONTACT or MOTION sensor.
It Looks at a sensor’s device class, and only looks at a limited number of device classes:
if attrs.get(ATTR_DEVICE_CLASS) in ( 'door', 'garage_door', 'opening', 'window', ): return self.TYPE_CONTACT if attrs.get(ATTR_DEVICE_CLASS) == 'motion': return self.TYPE_MOTION
My binary sensor was not any of these device classes so it wasn’t discovered.
Once I changed its device class to “opening” then got discovered.