Did you update any apps since updating to ios9 and when you restored them were they the newly updated apps that restored to your phone or were they the old versions that you had backed up since ios8?
Old versions that are already saved in iTunes will copy over to your phone, but once you update them on your phone they won't copy to iTunes and iTunes will only copy over the pre ios9 version.
Hmmm, actually, I have not updated any apps since I reinstalled iOS 9 yesterday.
But, some days ago, when I tried to install iOS 9 for the first time, by doing a restore and then restoring from my back up from iOS 8.4.1, it did not install the apps from iTunes, like it did now. It was saying "Preparing to copy items" and it kept showing the circle spinning on the status bar, so I unlocked the phone and noticed that it was redownloading the apps instead of copying them from iTunes.
Also, after it was done, what you're saying was happening - meaning, when an app was updated it didn't copy the newest version to iTunes, I had to download it on iTunes too, to get the copy over there.
So, since at this point, after I did everything from scratch, the apps did install automatically from iTunes, while previously they did not, I suspect that when I get an update, if I install it through my phone and then do a sync with iTunes, it's going to copy it over there automatically.
I will make sure to post what happened, when I get notified for an update of an app.