Although already correctly answered by VonC, just some additional details:
Git Extensions checks only the local config file to make this wrong and quite problematic assumption.
A local repository can have more than one remotes but it can only have a single branch section for each branch in the config file, mapping the branch to a specific remote (it would not make sense to map the branch to more remotes anyway, since the branch section is only used to simplify the push and pull commands, allowing you to omit the remote and branch arguments).
In a scenario (like ours), where more than one remotes are specified for a repository but of course the branch section only maps to one of them, this warning appears every time you try to push to one of those secondary remotes. It's okay if you are used to it, but it becomes problematic for those who see it first time, as it immediately gives the idea that something wrong is about to happen that should probably be avoided.
The message itself, is confusing. The way it's put, gives the idea that Git Extensions has actually connected to the remote repository, went through it and found out that the branch does not exist there. But this is not the case and the branches already exist in the remote repository's /refs. Git Extensions only checked the local config file, therefore the message provides false information.
Normally Git Extensions should indeed connect to the remote repository, before showing such a message but even in this case, there's nothing wrong in pushing a new branch, just as a push could also delete a branch in the remote repository, and in this case, since Git Extensions only checks the local config file, you possibly do not get a warning at all, although it's more dangerous than adding one.