Slow Queries On Large Databases

The post below speaks about slow querys using LIKE.
http://www.asprunner.com/forums/topic/13451-slow-queries-on-large-databases/pageviewfindpostp46535
And all the searches comes with "contains" constraints, and that´s does not works with my largests tables, with 40.000.000 or more records.
And we have another problem. If we change to "equal" instead "contains" the query comes with UPPER, and that makes the search extremely slow.
So we have this slow query using "contains":
SELECT COUNT()

FROM Comunicacao

INNER JOIN Celular ON Comunicacao.IMEI = Celular.IMEI

INNER JOIN Usuario ON Celular.Usuario_Usu_id = Usuario.Usu_id

WHERE (1=1) AND (UPPER(Comunicacao.IMEI) LIKE UPPER('%343580%'))
And this slow query using "equal":
SELECT COUNT()

FROM Comunicacao

INNER JOIN Celular ON Comunicacao.IMEI = Celular.IMEI

INNER JOIN Usuario ON Celular.Usuario_Usu_id = Usuario.Usu_id

WHERE (1=1) AND (UPPER(Comunicacao.IMEI)=UPPER('423671'))
Using "LIKE" I can´t see how make it fast, but if we can generate the querys without "UPPER" the querys gets 10 times faster, like this:
SELECT COUNT(*)

FROM Comunicacao

INNER JOIN Celular ON Comunicacao.IMEI = Celular.IMEI

INNER JOIN Usuario ON Celular.Usuario_Usu_id = Usuario.Usu_id

WHERE (1=1) AND (Comunicacao.IMEI='423671')
So the question is: How we can generate the querys WITHOUT the UPPER clause?