Merge sorting is an option, but if you really want to use Excel as the source for the SSIS lookup task, you can do it.
As you correctly determined, you cannot use the Excel Connection Manager in the search task, it only accepts the OLE DB Connection Manager. Then the trick is to use OLE DB Connection Manager with Excel spreadsheet.
In this example, I have a table with status codes and their full name, and my source data contains only abbreviations. This walk will do an Excel search task to get these values.
Observe these caveats: Lookups are case sensitive, regardless of whether the source database (or the file in this case) is case sensitive. Excel rows will always be interpreted as unicode / nvarchar.
Initial data
Given a simple file sitting on C: \ tmp \ LookupReference.xlsx, which looks like this: 
Connection manager
First we need to install the OLE DB connection manager. Instead of the standard "Native OLE DB \ SQL Server Native Client 10.0", this value will change to "Native OLE DB \ Microsoft Office 12.0 Access Database Engine OLE DB Provider". On the server or file name, find the source file. Pressing the "Test Connection" button at this point will result in an error.

Here comes the "magic." Go to the "All" tab and scroll up. In the advanced properties, add the specified line "Excel 12.0; HDR = YES; IMEX = 1;" This tells the provider that we will use Excel 12.0 (.xlsx format) with the title bar, and IMEX 1 reports that the driver will be mixed data.

Your package will now look something like this. Advanced Connection Manager defines and assumes an existing data stream

Data stream
To simplify things, I have a script source that generates 3 rows of data with the status codes MO, KS and NE and sends them down the pipeline. Your source will obviously be different, but the concept will remain the same. Sample code provided in the annotation.
In your conversion transform you will need to write a spreadsheet query. This is similar to a regular database query, except that your table will be Sheet1$ if you do not have a named range in which your table will be MyRange Note that $ is required when referencing a sheet. Using the above table, my query will be
SELECT S.StateCode , S.StateName FROM `Sheet1$` S
I map my task column <$ w370> StateCode to the StateCode column of the reference request and check the StateName field as I want to add it to the data stream.

I installed a data viewer after the search task to verify that my searches were processed

Everything works, and we are all happy.
Old excel
If you are using the .xls file, you need to make the following changes. - In the Connection Manager, instead of the Office 12 provider, select "Native OLE DB \ Microsoft Jet 4.0 OLE DB Provider", - Advanced properties become "EXCEL 8.0; HDR = Yes; IMEX = 1;"
Minor change
This is noted in Using Excel in SSIS Search Conversion . You can also use the Cached Connection Manager to use any search source in SSIS 2008 +