I was going crazy with this issue until I found the culprit. I added a second IP to the proxy connection in order to access a subnet. I didn't delete it but didn't remember I added it either. Guess what? I deleted the address and backups are running like a charm again.