Gregory,
> I just know I'm overlooking some real obvious thing but for some reason this 
eludes me. I could see if the search was very slow (the function returns type 
"text" and the indexed columns are of type CHAR().
Char(what?)  ?
if it's, say CHAR(4) that could be your problem;
'NM'::undefined == 'NM  '::CHAR
but
'NM'::TEXT != 'NM  '::CHAR
so casting everything to the desired type should fix the problem.
and why are you using CHAR, anyway?
-- 
-Josh Berkus
 Aglio Database Solutions
 San Francisco