We've got a 3.6.1 server (with approx. 70 agents), local SQL (2000). I know we have to upgrade SQL before anything else, but is there anything preventing us from simply standing a parallel 4.5 server with a new 2005 (or 2008) remote sql server, detaching agents from the 3.6.1, and redeploying from the 4.5?
Nope, nothing at all Effectively what you're doing there is a clean install, then deploying the agent from the new server over the top of the old one. In the situation you describe that's probably going to be the quickest and easiest approach.