One more thing you need to consider, unfortunately, is how trustworthy the former staff members are. If untrusted parties have access to the machines and you don't, this is a far more urgent issue.
in reply to Brute forcing account logins.
If they are trustworthy the first attempt should be contacting them, as others have said. Paying one of them for half a day is better than being locked out of the equipment.
Expect, Net::Telnet, Net::SSH2, and more might be good ways to try the passwords. Perl is a good tool if this is the route you need to take, but this is a path you'd really rather not resort to using.
If all else fails, you should be able to figure out enough configuration information with a protocol analyzer and port scanners to recreate the router, firewall, and switch configs on redundant equipment. Then, you just swap in the newly configured gear and reset the configs on the originals at your leisure. The actual servers are a bit trickier, but they are easier to get into with, for example, a live CD.
One thing this should teach your client (and teach you to teach your clients) is that backups of data are not enough, and that backups of configs are necessary too.