Does matter with negative mass exist? Or does it exist mathematically? 
Is it really inconsistent with a common-sense, mathematics or known physical laws? 
As far as I understand, if it exists, it must be far away from the "positive" matter because of repelling force, so it explains why there is no observations of such matter. 
It would be also very consistent with the idea that the total energy of the Universe is zero. Doesn't it imply that the total mass of  the Universe is zero? 
Can you please clarify the statements below that seem to contradict each other?
1) "all structures that exist mathematically exist also physically" -Max Tegmark.
2) Despite being completely inconsistent with a common-sense approach and the expected behavior of "normal" matter, negative mass is completely mathematically consistent and introduces no violation of conservation of momentum or energy.
3) Such matter would violate one or more energy conditions and show some strange properties, stemming from the ambiguity as to whether attraction should refer to force or the oppositely oriented acceleration for negative mass.
 A: 
As far as I understand, if it exists, it must be far away from the "positive" matter because of repelling force, so it explains why there is no observations of such matter.

For one, negative mass would still be attracted to positive mass, but the positive mass would be repelled. This would lead to the negative mass "following" the positive mass.
Why is this? The force is a repulsive one. But we also have the fact that $\vec F=m\vec a$. Since one of the bodies has negative mass, it will be attracted.
If there was a body of negative mass less massive (talking about absolute values here) than our positive massed-universe, it would move much faster and eventually "catch up" with ours.  If it had the same absolute value of mass, both would keep accelerating and it would never catch up. If it was larger, it would be left behind eventually.
The lack of any large quantities of negative mass in our universe excludes the case of a body of negative mass having caught up with us. The lack of any acceleration of the universe signifies that there isn't any large body of negative mass with absolute value less than or equal to the mass of the universe. So, if there is any large body of negative mass, it has larger mass than our universe and it is separated from our universe.


"all structures that exist mathematically exist also physically" -Max Tegmark.

This is a part of his MAthematical Universe hypothesis. Note that it's just a hypothesis, it isn't backed by much concrete evidence yet.

Despite being completely inconsistent with a common-sense approach and the expected behavior of "normal" matter, negative mass is completely mathematically consistent and introduces no violation of conservation of momentum or energy.

This is true--it lets one create energy out of thin air by introducing a body with negative mass to the system, but this doesn't conflict the principle of conservation of energy as the body has it's own energy become more negative.

Such matter would violate one or more energy conditions and show some strange properties, stemming from the ambiguity as to whether attraction should refer to force or the oppositely oriented acceleration for negative mass.

I'm not too sure about the energy conditions, I'm not strong in General Relativity. But the second half is just about some strangeness attached to it and some confusion regarding terminology (relating to what I explained near the top of this answer).

Finally, vacuum fluctuations (which exist) can have a net negative energy density, so these have "negative mass", in a way. But these aren't easy to harness with current technology.
A: No. Matter must have nonnegative mass for reasons of causality. This follows from relativistic quantum field theory, as it is impossible to define free causal quantum fields (modeling the asymptotic = observable bound states) with negative masses.
Speculations that there might be particles of mass_square smaller than zero (which would then always move faster than light) have been thoroughly discussed and tested in the literature, without any positive evidence. See the section
''What about particles faster than light (tachyons)?'' in Chapter A7: Time and space of my theoretical physics FAQ at http://arnold-neumaier.at/physfaq/physics-faq.html
A: So far no particle with negative mass have been discovered.
And scientific theories based on what we observe and meant to describe what we observe. 
We can plug in the numbers for negative mass but what we get doesn't mean it would make physical sense. It would be mere speculation.

The problem with negative mass that it would lead to runaway reactions.
First the negative mass would accelerate towards the opposite direction of the force acted upon it. This means a bullet with negative mass fired at a wall would go through the other side of the wall faster than it went inside. Air drag would make it even faster. Leading to a run-away system however small amount of negative mass we speak of. A tiny bullet and its shards would eventually destroy everything as it get more and more negative kinetic energy.
That's not good.
A: So far as we know $m \geq 0$ --all observations are compatible with this--.
Mathematically you can imagine negative masses, imaginary masses or many other masses, but this does not mean they are real.
No, negative mass is not consistent with the idea that the total energy of the Universe is zero. This zero of energy is because gravitational energy is negative and in the free-lunch cosmology compensates the positive energy associated to matter giving a zero total energy. Zero energy does not imply zero mass or vice verse; for instance photons have zero mass but positive energy.
The quote from Max Tegmark looks particularly misguided to me. In his lectures on physics Feynman explains the difference between physics and maths.
How do you know that a negative mass "introduces no violation of conservation of momentum or energy"?
A: 1.The motion of negative mass and positive mass

Negative mass has both negative inertial mass and gravitational mass.
Negative mass is accelerated in the direction of positive mass, and positive mass is accelerated in the direction to be far away from negative mass.
If the absolute value of positive mass is bigger than that of negative mass, they will meet within finite time(attractive effect). If the absolute value of positive mass is smaller than that of negative mass, the distance between them will be bigger, and they cannot meet (repulsive effect).
This property is very important. Negative masses are gravitational bounded to massive positive masses (Galaxy or cluster of galaxies) for massive positive mass has attractive effect on negative mass.
One of problems regarding movement of negative mass, which researchers are likely to misunderstand is that if there are negative mass particles around the earth (or galaxy), large positive mass, they may not fly to the universe, but fall to the earth (or galaxy).
2.The motion of negative mass and negative mass

Both two objects are accelerated in the direction of +r^ which extends distance r, so as time passes, the distance between them is greater than initially given condition, and the force between them is attraction, but the effect is repulsive. The force is attraction(-Gm1m2/r^2), thus the potential energy between them has negative value.

As far as I understand, if it exists, it must be far away from the "positive" matter because of repelling force, so it explains why there is no observations of such matter. 


Negative mass(energy) is accelerated in the direction of positive mass(energy), and positive mass(energy) is accelerated in the direction to be far away from negative mass(energy). 
But,
1) If the absolute value of positive mass is bigger than that of negative mass, they will meet within finite time (attractive effect) 
2) If the absolute value of positive mass is smaller than that of negative mass, the distance between them will be bigger, and they cannot meet (repulsive effect).
I made simulation video on negative mass's motion
http://www.youtube.com/watch?v=MZtS7cBMIc4  : refer to 00:00 ~ 02:40s
