I do not need a solution for this - I am posting it for interest and perhaps save somebody some time.
I have a lengthy stored procedure (no parameters but far too long to post) that prepares data for letters. It works off a master table of addressees which contains a flag to indicate whether that record has been processed. Each run processes a fixed size batch of records and sets the flag. The next run then goes on to the next batch for which the flag is not set.
Testing this in Query Analyser (SQL7), it works fine until it runs out of records in the master table. On the next run, without any changes to the code, it throws an 'Internal Query Processor Error: The query processor could not produce a query plan.'. I have confirmed that this only occurs when it has nothing to process. Presumably, the query processor can't identify any statistics to work with and just gives up! Why it is recompiling anyway, I've no idea.
I've just wasted a few hours trying to rewrite perfectly valid code!