I wonder how much the indexes are helping. It sounds like it could be a hard case for a query planner. You might be doing more full table scans than you realize, and it might not be as slow as you might expect. I think regex searches do full scans, so that gives an idea of the cost.

This is a great problem that would be fun to work on. Except that I guess you already found a satisfactory solution.