oh 25k rows should have been only a few minutes at most unless the database is being pounded.
my guess is that it is not your partParentID then, but the columns you are joining on. indexed integer columns are about as fast as you can get. remember that an INNER JOIN is basically a WHERE, but you are saying WHERE tableA.column = tableB.column. So indexing is relevant there as well.
The only other thing I can think is that its not actually the database, but an outside process running at the same time, abusing the CPU or ram. If its part of a CF routine your running, thats your problem, its that your still using Cold Fusion...

jk
But that could be it. I have many times been blaming things on my database, but later to find out that its actually my non-db code screwing it up, or even some other process. It sounds like you are running in query analyzer though, so that wouldnt be it, unless you do have some routines running. watch your proc and ram while running your query and see whats going on.
one other thing is to run the query through the "estimated execution plan" (cntl-L from the query analyzer) which will show you what part of your query is going to use the most juice. that can help to point you in the right direction.