Are you in a multi-site environment? We have had additional MRP struggles due to some part revisions being mfrd in one plant vs another. We would get empty jobs when a phantom part had a different partrev plant than the parent, prior to upgrading to 10.1.600.20, and the MRP took twice as long.
Also, I believe there were some minor upgrades to 10.1.600 that addressed some of the MRP issues and might not be too difficult to upgrade to.
Perhaps you should turn on detailed MRP logging and review where the time appears to get stuck and where errors occur.