Thanks for your answer, Rui.
That's sort of the conclusion I came to - the Contact has to be associated with a site.
Could you help me understand the most direct way to achieve that in code? I see UserSiteInfo which depends on a USER instead of a contact. Am I looking in the wrong place, or is there another step or two the get from Contact to User?
EDIT: This was actually straightforward. By setting the ContactSiteID on the ContactInfo, the Contact was correctly associated with a site and the workflow instance was able to properly start.