The first thing to be aware of is that iTunes uses a unique "Library Persistent ID" to identify the pairing of an iDevice to an installation of iTunes. This 16-digit hexadecimal id is stored on both the device and the computer it is paired with. iTunes generates a new id when it is installed (or more accurately, when it builds its library). If you plug in an iPhone that has a different persistent id than the copy of iTunes installed on that computer, you will get the warning dialog shown above.
The only thing standing in your way, however, is that darn persistent id. To get things working smoothly, we need to hack the installation of iTunes so that it thinks its id is the same as the one on our iPhone.
To do that, we first need to figure out what our phone's persistent id is. There are a couple options here, depending on whether or not you have the original synced copy of iTunes still available.
Step 1: Getting the Persistent ID
If you still have the original installation of iTunes that your iDevice is synced with, you can grab the persistent id from the "iTunes Music Library.xml" file in your iTunes directory. Just search for the "Library Persistent ID" tag.
If you no longer have access to that previous installation (as was my case), you need to get the id from your iPhone itself. Luckily there is a sneaky way to do this without having to jailbreak your phone. [If your phone is already jailbroken, you can read it from one of the .plist files in your iTunes directory on the phone, I believe.]
The trick is that you need to do a backup of your phone using iTunes and then dig into the backup files to find the persistent id. Fortunately iTunes lets you perform backups without being synced, so you can backup an iPhone on any copy of iTunes.
Unfortunately, the id is not plainly visible in the backup files. You will need to use a free web script to determine your persistent id from an Info.plist file you upload.
Full instructions are on this page.
Now that you have your library persistent id, you need to trick your installations of iTunes into thinking that that id is actually the id it has.
Step 2: Changing iTunes' Persistent ID
iTunes stores the persistent id in two places, just to make it trickier for us to change: once in the "iTunes Music Library.xml" file already mentioned, and once more in the "iTunes Library.itl" file, which is a binary file and much trickier to edit.
Although it is (or at least was) supposedly possible to edit the binary file and get it to accept the change, I have not been able to get this to work, so I don't recommend bothering since there is an easier way that doesn't require it.
First, backup the two aforementioned files. Next, open the xml file and paste in your library persistent id obtained from step 1 over the existing id in the
<Library Persistent ID> tag and save.
Now create an empty file and name it "iTunes Library.itl". It won't work if you just delete or rename the file. iTunes needs to think it's become corrupt, not just disappeared.
Now when you start iTunes, it will see the "corrupt" library file and will rebuild it for you, from the xml file which contains your new persistent id.
If all goes well, after a few minutes of rebuilding your library file (it can take quite a while if you have a large library, mind you), you should be able to plug in your iPhone and sync as if nothing were wrong in the world!
For more details (including how to find the iTunes directory on your computer), read this page.