This might not be the solution in all cases, but for me it's one of the hypotheses I've tested and found true:
I noticed that for private/public repos where I was admin, integration happened smoothly. It's only for repos where I had only read-write-access that I couldn't setup the deployment from version control (that is for Bitbucket and Azure Websites).
Actually, to test this hypothesis, I made a fork of a repo where I have only rw-access (in the fork, am automatically made admin), and then tried setting up deployment with this fork. It worked fine!
Note that for all the repositories I tried linking to (whether private or not, and whether the linking worked or not) I had read-write access. Though, I believe the ultimate setup should only need read-access to a repo. Am yet to isolate the actual problem...