Well, you will sure be surprised to find out what an actual reason is.
I ended up revoking all certificates, removing profiles, going all the way from CSR to setting up a build environment. I did experiment with entitlements and 'get-task-allow' and other stuff. But none of that did the trick.
At some point I decided to have another look at IIS server and plist file used for distribution.
So here it goes, the problem was with plist file.
The iTunes artwork image file was named "iTunesArtwork.png", the url in plist file was http://hostname/Mobile/iOS/iTunesArtwork
.
So I renamed the file to "iTunesArtwork" (removed extension), that didn't fix the problem, but I could now see the installation progress bar getting almost to the end and status message changing from "Downloading" to "Installing". Before that it failed at the very beginning, right after saying "Wait".
Finally, I put all that stuff in order, named the file "iTunesArtwork.png" and fixed url to be http://hostname/Mobile/iOS/iTunesArtwork.png
And that's when it worked.
I could only come up with the following explanation:
Before an installation starts, iOS is checking if all urls in plist point to valid resources. If any of that fails, iOS 5 aborts installation, while iOS 6 can at least tolerate invalid artwork url.
During an installation, iOS first fetches app icon to display it on the screen, then downloads the ipa file, and in the end fetches artwork. Here, again, iOS 5 has stricter validation rules, it won't like names like 'iTunesArtwork', I think it just doesn't like file name with no extension. If fetching artwork fails the whole installation on iOS 5 is aborted. iOS 6 seems to ignore errors at this stage.
I personally think that iOS 5 does it the right way. It is a good thing to validate that all urls are valid and all files have proper extension. If both iOS versions did it the same way, I would stumble upon the problem at the very beginning.
UPD
Just tried with apache web server setup running on Mac OS X 10.8. Can tell for sure, unlike IIS, with apache iOS 5 tolerates missing extensions quite well, so it's not just iOS 5, but a mix of iOS 5 and IIS that causes all the trouble.
However, if I put stuff like http://hostname/Mobile/iOS/NoSuchFile
in plist in place of artwork, then iOS 5 will fail to install OTA, while iOS 6 won't even notice a thing and proceed with installation.