Piece of cake. Leave computer idle and look in the router or using CurrPorts utility for in/outbound connections, write down the IP and google them or find destination network to see if it's suspicious.
Assuming the root kit is stupid enough to communicate all the time, as opposed to staying dormant until a certain point in time or passive trigger. Something like CurrPorts is obviously useless, any half decent root kit will cloak its files and sockets.
If IP has not been flagged yet by anybody else, plug the HDD into a 2nd PC and do a file content search for the IP in plaintext and HEX formats, checking if files are compressed like UPX/ZIP/BZ/RAR etc for example and decompress them before doing binary search.
Assuming it's using regular files for storage, and not free space or some other form of non-volatile storage like EEPROM.
If the rootkit is encrypted and polymorphic, most decent antiviruses will flag the code that does decryption. Yes, they are hard to get rid of but not THAT hard.
If it's just about obfuscating an IP address, something simplistic like rot13, XOR or NOT would be sufficient, and unlikely to be flagged as encryption.
Because modern antivir companies have true hackers working there in the proper meaning of this word, the game is different now. Virmakers are always step ahead because they try to write something NEW, but antivir guys know most of the tricks, so even new shit can be killed of. The antivir companies have dozens of highly competent hackers working for them, while number of equal skill virmakers is very small.
Anti-virus software is fine if you're not in the first group being infected (they need time to receive samples and send out new signatures), but it's by definition reactive. If the attack is very targeted, like Stuxnet, detection by anti-virus companies may also be hard. Do (did) they keep SCADA systems with the required Siemens hardware around as honeypots? I believe it took at least a few months from the release of Stuxnet to discovery by a security company, that's a few months time to wreak havoc. Even with large-scales worms which are detected faster, there's still a window of opportunity to infect systems before anti-virus will become active, and as soon as the system's infected, detection by anti-virus may be very hard.
Yes, most of us are low-profile targets who are not likely to be a subject of a targeted attack, but don't kid yourself that you're safe, it's just that nobody cares enough.