I would go with what Sean Lange recommend first.

In no particular order:

Try #1:

If you can I would change the table convert data type to VARCHAR(26) and check the performance result if it changed.

(The query looks only for the 25 first characters regardless of the remaining ones so I would avoid taking more than necessary)

Try #2:

However if this is not possible, I would try adding a persisted computed column having the result of your where clause condition in it and outputting a bit if it satisfies the predicate or not.

It would be computed only once per row and you will be able to filter on that computed column (even be indexed if necessary even thought indexing a bit is arguable).

It might also fall into the same issue the initial query as the first time it is added, but I feel it would worth a try.

Try #3:

Is this a heap table? Could forwarding pointers be the cause if that column has several modifications done on it?

Try #4:

Would it be possible to isolate the database and avoid running it into 2000 compatibility mode and let it alone run on 2008 compatibility mode just for this particular issue?

I would like to know if that issue occurs only with the compatibility mode option or if this also occurs natively to SQL 2008.

Try #5:

Try moving out the table value function, they often gets it the way of performance.

Let us know, the more details we have the better our suggestions will be.