ha! a real tricky one there. I've encountered some of these problems and resolved most of them before. you've been given some wrong advice however. The mem to leave area is indeed a problem with 32 bit systems - have you considerd going to 64bit?

The maint plans issue is correct if you;re using sysmaint.exe ( sql 2000 ) as this and the xmlprepare and dtsrun all run out of process and this is what can screw things up. large plans are also a problem. try to limit the out of processes programs - please tell me you don't have the 3gb switch enabled.

16 procs ? cores . cpu's or + HT?