I think you're falling victim to the way that SQL Server handles store procs.

What happens if you do something like this:

select TOP 500 * 
from dirmaster
where 
(name is null or name like RTRIM(@name))
and (tele_no is null or tele_no like RTRIM(@teleno))
. . .

If you are still have issues, you might want to create the proc with the WITH RECOMPILE option.

-Mike