BOL says it all:
ROBUST PLAN -
Forces the query optimizer to attempt a plan that works for the maximum potential row
size, possibly at the expense of performance. When the query is processed,
intermediate tables and operators may need to store and process rows that are wider
than any of the input rows. The rows may be so wide that, in some cases, the
particular operator cannot process the row. If this happens, SQL Server produces an
error during query execution. By using ROBUST PLAN, you instruct the query optimizer
not to consider any query plans that may encounter this problem.
so, you are encountering a condition where sql server is choosing a plan, when
that plan is used to try and get results, it turns out the plan is not acceptable
as assumed bounds are surpassed, so the query fails, so when you add the ROBUST
PLAN option as a query hint to your query, the plans where this happens are
discarded, which means a slower plan that is guaranteed not to surpass the assumed
bounds is selected.
Alos make sure you have give sql2k sp2 a go??