emerge -s <package name> takes 35 seconds on my Pentium III @1500MHz system with 0.5G RAM which isn't running anything else that uses disk or memory significantly (except X and fvwm). I suggest to remove some cause that is making the database search slow - used data structure or maybe slow interpreted language.
*** This bug has been marked as a duplicate of 100714 ***
There are lots of tools that are optimized for this type of search. For example, esearch, eix, and qsearch (portage-utils).