Okay I got this working with minimal fuss. Here's what you have to do:
1. Download the iPhone Configuration Utility 3.5 installer for Windows, but don't install.
2. Download 7-zip and install it
3. Open the iPhoneConfigUtilitySetup.exe in 7-zip and extract the AppleMobileDeviceSupport.msi (version 5.1.1.4) installer.
4. Open AppleMobileDeviceSupport.msi in 7-zip and find and extract MobileDevice.dll (version 507.7.0.1) and copy it to the iPhone Configuration Utility folder (for me it is "C:\Program Files\iPhone Configuration Utility". It's the folder that has iPCU.exe in it). Do NOT copy it into the Mobile Device Support folder.
Basically IPCU needs the old version of MobileDevice.dll.
That's it. Now both IPCU and iTunes 7 should work without having to keep moving files around. At least it does for me.
Edit:
If you don't feel like going through the above steps, I uploaded the old MobileDevice.dll to Dropbox so you can simply grab it from https://www.dropbox.com/s/lzr2rcz3i5zmb6o/MobileDevice.dll