Going Crazy With Inconsistant Batch Duration

First; thanks for looking.

On SQL Server 2000. IBM X series, dual 2GHz Xeon processors, 3GB RAM, RAID 5 DB array and separate Mirrored drive for OS, Windows 2000 Server.

Note: I should have moved the log files to the mirrored volume - I only just noticed it wasn't like that ... oops.:o It only has the OS and backup files (different logical volumes).

Problem: I have a Bill of Material system. It has a batch (Stored Procedure) that explodes Order Line Items. Each line has about 40 components.

The SP has 5 major steps to explode the Assembly, figure out colors/sizes to get the actual part numbers, assign quantities, update flags on the line item table (that has 3,500,000 rows but is not a clustered index - fill factor 85% on the unique autonumber index I use for the updates). The SP is jam packed with User Function calls, sub-Stored Procedures, and (yes) some cursors (on small declared temp tables created for each Order Line processed).

The execution plan for the whole batch of 100 is humongous - like 1000 pages, however nearly all steps are about 16 - 40 milliseconds to execute.

It normally takes 13 seconds to process 100 line items (3900 assembly rows created). However; about every 20th run, it takes 2 or 3 minutes ON THE VERY SAME LINE ITEMS. No programming changes! Run back-to-back, or with a minute or two delay. Then running it again, back to 13 seconds. Sometimes it takes 25 or so seconds, but that oddball 3 minutes is a killer.

I put some timing INSERTs into a temporary log file to localize the problem.

So; here's the REALLY weird thing. The part that experiences the intermittent 2 minute delay is a VERY SIMPLE call to a SP that INSERTs to the tbBATCHs table and gets the identity and passes it back with an Output variable. The tbBATCHs table only has about 8 columns. Nobody else uses it so it's not locking. It has an "If Exists" selection following the Insert to see if another batch is in progress not yet flagged as complete, but's not the issue because it's never true (hard coded values for testing forces this).

I have a Standby Server (duplicate config of main server) so I ran it there. Same issue.

If I loop 100 times on the tbBATCHs INSERT SP, it is pretty quick (like 2 seconds for all 100).

It's never on the first run, so I think it may be some sort of Log File catch-up.

Also; I DO NOT have Transaction Logging in place yet.

Ideas?