Recent studies of queries submitted to Internet Search Engines have shown that non-English queries and unclassifiable queries have nearly tripled during the last decade. Most search engines were originally engineered for English. Although in recent years search engines have improved their handling of non-English queries, studies show that many problems still exist and are worthy of further research. The primary aim of this research study is to present an evaluation methodology for identifying the shortcomings and measuring the effectiveness of search engines with non-English queries. The focus of the research is on the Greek language but the findings and methods could be applied in other non-English and non-Latin languages.