OK, found the issue. In the ajax-search-pro/backend/settings/class/customtaxonomyterm.class.php script there's this line:
$terms[$taxonomy] = array_slice($terms[$taxonomy], 0, 50, true);
When I changed the length parameter from 50 to 100, the missing terms showed up.
So here's my question: is there a particular reason why this was limited to 50? Since this was a problem for us, is there any way for this to be addressed in a patch?