What I ask myself is: Couldn't there be "negative" bundles of mass just the other way that pushes matter away instead of invisible dark matter that pulls it?
The galaxy rotation curve indicates a (positively massed) dark matter distribution that is close to spherically symmetric; cf. dark matter halo. I take it that you are asking whether instead of modeling it as a positive-mass distribution around the galaxy, we can model it instead as a negative-mass distribution surrounding the galaxy pushing the stars inward.
No, that's not possible. Since the effect is spherically symmetric, the hypothetical negative-mass distribution would need to be spherically symmetric as well. However, Newton's shell theorem guarantees that everywhere inside a void surrounded by such a distribution with this symmetry, whatever the sign of the mass is, the gravitational force vanishes. So a negatively-massed dark matter distribution outside the galaxy would do nothing at all.
In general relativity, the analogous statement is guaranteed by Birkhoff's theorem, and although GTR is nonlinear (and there are stars in the way), in our galaxy gravity is weak enough to be handled by the linearized theory.
What is the proof for the fact "Gravity is always attractive" beside that fact that it seems to be?
In general relativity, gravity doesn't have to be attractive. For example, inside a perfect fluid with density energy $\rho$ and pressure $p$, $\rho+3p<0$ would imply that gravity is locally repulsive in the sense that a ball of test particles initially at rest expands rather than contracts under gravitational freefall. More generally, the strong energy condition characterizes whether or not gravity is attractive in this sense.
However, there is no known material that violates the strong energy condition, besides possibly dark energy, which is a cosmological constant in the standard ΛCDM model, as Gerald says.
Has someone tried to find something like that?
There are many studies and simulations that consider dark matter with a nonzero pressure component, sometimes even anisotropic pressure components. For example, "hot" dark matter would have $p\sim\rho/3$, while "cold" dark matter would have $p\sim 0$, "warm" dark matter somewhere inbetween. The CDM in the ΛCDM model stands for "cold dark matter", naturally.
There are more exotic possibilities with anisotropic pressure components, etc. But I don't know of any paper that looked specifically for $\rho<0$ dark matter, and for the above reasons I'd be surprised if one existed.