How many single email messages with visualforce templates can be sent in a single transaction?

Messaging.SingleEmailMessage needs one contact per template in order to merge the data correctly (including Contact-specific information). The good news is that Messaging.sendEmail supports at least 10,000 emails in a list, so all you really need to do is create a list of messages and send them all at once:

Messaging.SingleEmailMessage[] messages = new Messaging.SingleEmailMessage[0];
for(Contact record: [SELECT ... FROM Contact ...]) {
    Messaging.SingleEmailMessage m = new Messaging.SingleEmailMessage();
    m.setTemplateId(templateId);
    m.setTargetObjectId(record.Id);
    messages.add(m);
}
Messaging.sendEmail(messages);

Note that there is a daily limit of 5,000 emails send to Leads and Contacts through Apex Code, so even though Messaging.sendEmail supports a much larger number of emails, you'll get a LimitException if you try to email more than 5,000 rate-limited records in a 24-hour period.

Searching a little bit longer I've found that my issue is not related to the SingleEmailMessage class itself, but on how Salesforce handles the insertion of the email records when saveAsActivity is set to true on the message.

Salesforce does not bulkify this insertion, so when you try to send more than 100 emails and set them to be a record related to your object, the platform inserts one Task object after the other, and eventually it breaks its own DML limit of 100 transactions.

The solution is to send less than 100 emails for now, or use some kind of scheduled job to run multiple times successively, if you need to save the email on the platform. If you don't need the email stored, then you can set saveAsActivity to false.

If you are reading this and having the same issue, please vote for this idea which proposes that this insertion to be a bulkified process.