I found the solution by not using any UPPERCASE characters in the search.
Searching for lowercase characters, even if the data fields are uppercase, solved it.
Example code that worked:
$query = new Zend_Search_Lucene_Search_Query_MultiTerm();
$query->addTerm(new Zend_Search_Lucene_Index_Term('en', 'language'), true);
$query->addTerm(new Zend_Search_Lucene_Index_Term('us', 'country'), true);
$hits = $index->find($query);
The data fields have the values "EN" and "US" and have been indexed as such and the document output confirms this but the search requires a lower case input for some reason.