This actually sounds like this might be a problem that MS SQL Server has when the index keys correlate closely to the actual tables. In such cases, the optimizing engine may choose to ignore the non-clustered indexes, thus costing much more than it should.
Since you can use the Query Analyzer, I suggest you run the 2 different select statements above using the cost estimator in Query Analyzer to see if the cost and execution plan changes with different index changes. First, add a new multi-column index that includes the Topic_ID, Author_ID, Thread_ID, and Message_Date. Test the performance of the query sorted and unsorted, also sorted on Thread_ID and then on Message_Date. Change the order of the fields in the index too.
I'm building a large test table to evaluate the costs associated with the different indexes. I think a stored procedure that includes a cost limit override will be an effective work-around.
One interesting possibility is to open a new connection instead of using the persistant connection. I wonder if SQL Server is aggragating the costs of all the queries on the persistant connection. So, maybe if you open a new connection, SQL Server will estimate that cost by itself. I have NO idea if that's the case, but it's a quick experiment that can't hurt anything. To do this, open "delete_post.asp" and find line 217. It should say: "rsCommon.Open strSQL, adoCon". Change it to "rsCommon.Open strSQL, strCon", and save and upload it.