In order to post a full solution, I summarize my findings here:
When using a feature service as the source of records in a 'search()' appearance option, the dataset is pulled into a JSON object that is then searched when the user opens the drop-down list or starts typing (if 'autocomplete' is included in the appearance column).
If the maxRecordCount on the map service is not large enough to allow all records to be ingested into the JSON object, the drop-down list will only show the maxRecordCount of records, thus not the full list of records. Similarly, if 'autocomplete' is included in the appearance column, the matching of the search term to the records will be limited to only the records that were brought across to the JSON object.
The searchType parameter does not work. Thus, the search term that you enter into the search field (if you have autocomplete included in the appearance column) will be matched to any text within the records, e.g. searching for '201', will return both '201 N Broadway' as well as '100 N Broadway, Unit 201'. However, the records will be returned in the order in which they are stored in the database table, i.e. if the records are stored alphabetically (as I have them) then '100 N Broadway, Unit 201' will be returned before '201 N Broadway' is.