On twitter I asked you if this sproc does anything "special", such as XP calls, full text search, linked server, openquery, xml, etc. Are triggers in play?

Too bad it is intermittent ... can't comment out code sections to isolate the cause.

As @sqlsoldier said, you may need a support ticket to get to the bottom of this one, or at least someone familiar with debug symbols and stack dump analysis of SQL 2000.