The goal of this paper is to propose, evaluate, and compare four search strategies for ensemble feature selection, and to consider their application to medical diagnostics, with a focus on the problem of the classification of acute abdominal pain. Ensembles of learnt models constitute one of the main current directions in machine learning and data mining. Ensembles allow us to get higher accuracy, sensitivity, and specificity, which are often not achievable with single models. One technique, which proved to be effective for ensemble construction, is feature selection. Lately, several strategies for ensemble feature selection were proposed, including random subspacing, hill-climbing-based search, and genetic search. In this paper, we propose two new sequential-search-based strategies for ensemble feature selection, and evaluate them, constructing ensembles of simple Bayesian classifiers for the problem of acute abdominal pain classification. We compare the search strategies with regard to achieved accuracy, sensitivity, specificity, and the average number of features they select.