Is Pauli-repulsion a "force" that is completely separate from the 4 fundamental forces? You can have two electrons that experience each other's force by the exchange of photons (i.e. the electromagnetic force). Yet if you compress them really strongly, the electromagnetic interaction will no longer be the main force pushing them apart to balance the force that pushes them towards each other. Instead, you get a a repulsive force as a consequence of the Pauli exclusion principle. As I have read so far, this seems like a "force" that is completely separate from the other well known forces like the strong, electroweak and gravitational interaction (even though the graviton hasn't been observed so far). 
So my question is: is Pauli-repulsion a phenomenon that has also not yet been explained in terms of any of the three other forces that we know of?
Note: does this apply to degenerate pressure too (which was explained to me as $\Delta p$ increasing because $\Delta x$ became smaller because the particles are confined to a smaller space (Heisenberg u.p.), as is what happens when stars collapse)?
 A: As with a lot of other things, the trick rests in the nuances of the definitions.
Force is a well-defined concept. What it means is an interaction between two or more objects which contributes to a change in their momentum. The quantity of force is defined as the vectored size of this change:
$$\mathbf{F} = \frac{d\mathbf{p}}{dt}$$
. Now this statement also carries over to quantum mechanics. The difference is momentum is now an operator on the Hilbert space, $\hat{\mathbf{p}}$, instead of a simple vector. But we can still define the quantity of force, $\hat{\mathbf{F}}$, in the same way, via the Heisenberg picture in which it is the operators that are changing and not the quantum state vector. Note that the momentum operator doesn't always change! For an isolated system where momentum is conserved, its non-doing so is exactly how conservation of momentum expresses itself in quantum theory.
The Pauli exclusion principle is a principle regarding how a joint state vector of a composite system of a certain kind of identical particles is to be built up from those of the individuals. As it only is talking about state vectors, it does not imply any change in the operators, thus by implication no change in the momentum operator, and thus is not a force.
The normal force does indeed have something to do with the PEP, but it's more like a "team job" between both the PEP and electromagnetism. PEP sets a limit, and electromagnetism provides the actual force - the $\frac{d\hat{\mathbf{p}}}{dt}$ - to "enforce" (:D) it.
A: I'd like to add a different take on essentially the same as Anna's answer. I am writing to clarify the especial things that gave rise to my own personal misconceptions, so likely not everybody is going to benefit from this answer.
What is the fundamental force involved when you try to squash fermions together? It's whatever is confining fermions! You need to think of an ideal gas. When the molecules in the ideal gas are in flight between the walls, there is no force on them. Whatever force holds the walls and piston in place is the force that imparts the impulse to them to rebound them back into container. Likewise, the particles in the Fermi gas in the infinite square well are in the quantum mechanical equivalent of motion. It is the force shaping the infinite potential well that imparts the impulse needed to rebound them back into the well. Sometimes like you I feel the need for a Pauli "force". I think where I trip up here is that my everyday experience of solids is, well, they are solid!
So I kind of forget that the particles in them are in a dynamic state. They are in motion and by Newton II they need force to keep them confined. I and civil engineers tend to think of squashing a block of iron as a problem in statics, so we tend to think that if we are crushing something seemingly "static", there must be a balancing force thrusting back. Actually, when the crushing force gets really big, this everyday viewpoint breaks down: the problem is more one of dynamics. There is no backthrusting force. The particles are in motion and the crushing force from the outside is continually changing their state of motion, by Newton II, and thus keeping them confined. Or, if you like, in a D'Alembertian mindset, there is a backthrusting force but it is an inertial force arising from thinking of the problem from an accelerated frame.
Actually the ideas work equally well for bosons as for fermions. If you confine light in a perfect resonant cavity, there is a backthrusting force and it varies inversely with the resonant cavity's volume.
The difference is that, owing to the Pauli exclusion, the force needed to keep particles in their dynamic confined state in a given volume is MUCH bigger for fermions  than for bosons.
The Fermi gas in a container model applies when all other forces (electromagnetic, for example, that help arrange solids into crystals and so forth) are very small relative to outside forces crushing the solid. I have heard (I don't have direct experience of this) that in certain kinds of explosive analysis, especially the worthwhile analysis of the evolution of a nuclear explosion in a weapon, you can just assume that everything is a gas, with negligible error. You can simply think of the crushing force and the particle dynamics in the presence of this force and ignore everything else: interactions between the particles fade into the background.
Lastly let's look at the core of a body made up of charged fermions. I am NOT an astronomer so I've no idea of the exact numbers in the following diagram, which is to be taken with a grain of salt given that I heavily mix classical (GR) ideas with quantum interactions.

Let's assume our fermions are at first so energetic that a swarm of them doesn't collapse, and at first let's assume a low density. So we look at the top graph in my diagram, where I have drawn some paths of classical particles near the centre of a uniform swarm of them. You may know that in Newtonian gravity, near the centre of a uniform density body, the gravitational force makes for a simple harmonic oscillator potential, so the particles are taking the sinusoidal paths with time.
In the bottom two diagrams, I zoom in on a few "periods" of our classical particles. In a GR description, there is no force on them: we assume the swarm is like a GR "dust" so their aggregate effect is to curve spacetime as though they were a fluid continuum. Their energies will "thermalise" (i.e. follow roughly a Boltzmann distribution) and if the density is low, there are very few interactions between them. As I said, I am not an astronomer so I don't know whether we one can have a gas of fermions that is both (i) dense enough to curve spacetime so that the gas stays confined (bottom right diagram) and (ii) yet sparse enough that there are few interactions between particles. But what's important here is what happens as we "turn up the density" of our swarm by adding more matter. Now the fermions follow their spacetime geodesics only in little hops (bottom right diagram): very often they interact by swapping $\gamma$s. If you zoom in on these interactions, you get Anna's diagram: the "blue" and "green" fermions swap "red" (colours added only to tell the classical particles apart in my diagram) $\gamma$s. The fermions thus kick each other from one spacetime geodesic to another, and thus make jagged zigzag, highly non-geodesic paths through spacetime. So the shape and distribution of the swarm will change from being having its distribution being scaled down inversely with density as in the classical, noninteracting swarm case to something that is limited in density.
The Pauli exclusion principle governs how often these interactions (in this case electromagnetic) happen and can thus be thought of a constraint on a given problem - akin to boundary conditions and other information needed to fully define a situation - in this picture.
A: The QM notion of a "force" is highly technical jargon that doesn't match up with how the word force is used in the world at large. Basically, the notion of a "force" in QM is defined to be an interaction mediated by force carrier particles and therefore the exchange-interaction is arbitrarily defined not to be a force. Likewise, gravity is not a "force" because it doesn't work via exchange particles but instead works through curving space-time.
So yes the exchange interaction is a force. No the exchange interaction is not a QM force. Physicists who argue that the exchange interaction is not a force have confused the meaning of their jargon with the meaning of the word force in the minds of the common person and are making a prescriptavist mistake.
A: The pauli exclusion principle is not a repulsive force. It applies to fermions. It says that two electrons cannot occupy an energy state in a potential well with exactly the same quantum numbers. They have to differ by at least one quantum number. It is the Pauli exclusion principle that organizes the electron shells filling them sequentially from low to higher energy levels in atoms, otherwise they would all pile up at the lowest energy level.  Also the periodic table of elements filling the baryons in the strong potential well. It makes matter as we know it.

Yet if you compress them really strongly, the electromagnetic interaction will no longer be the main force pushing them apart to balance the force that pushes them towards each other. Instead, you get a a repulsive force as a consequence of the Pauli exclusion principle. 

The above is a misunderstanding.
It is not a force, since at the particle level forces have carriers that are exchanged between particles so that momentum and energy change.
In your "compression" description there is a continuum and not a quantized state so the PEP does not apply. When one scatters an electron on an electron one can get very close until the exchange particle ( the photon in this case)

 transfers enough energy in the center of mass system to start creating other elementary particles. The process is accurately described by quantum electrodynamics.
A: 
So my question is: is Pauli-repulsion a phenomenon that has also not
yet been explained in terms of any of the three other forces that we
know of?

$\def\ket#1{|#1\rangle} \let\up=\uparrow \let\dn=\downarrow 
 \def\PD#1#2{{\partial#1\over\partial#2}}$
There is no repulsion and no unexplained force. I would also add that PEP is an outdated way of describing the matter. In QM you should rather speak of antisymmetry of fermion states. It's only when we build up a many particle state as a tensor product of one particle states that antisymmetry forces us to keep only different states for each single particle. A simple example with two particles will explain this (I hope).

Two identical fermions in an infinite well
Consider particles in one dimension, constrained in a segment $0\le
x\le L$ (what is usally called an "infinite potential well"). Energy eigenfunctions (standing waves) are sinusoidal waves vanishing at boundaries:
$$\psi_n = \sin {n\,\pi\,x \over L} \qquad (n = 1,2,\ldots)$$
(these aren't normalized, but it's of no consequence for my present purposes.) The corresponding energy eigenvalues are
$$E_n = {n^2 h^2 \over 8\,m\,L^2}.\tag1$$
A short derivation follows, which you may skip with no harm.

$\psi_n$ has wavelength $2L/n$, then momentum
$$p = {h \over \lambda} = {n\,h \over 2\,L}.$$
Then energy (only kinetic) is
$$E_n = {p^2 \over 2\,m} = {n^2 h^2 \over 8\,m\,L^2}.$$

Assume your particles are non-interacting spin 1/2 fermions. Then above expression for energy eigenfunction is to be supplemented by specifying the spin state. Then Dirac's ket notation is preferable:
$$\ket{n\up} \quad \hbox{or} \quad 
\ket{n\dn}$$
both belonging to $E_n$ eigenvalue.
If your system consists of just two particles, a set of base kets would be obtained by taking tensor products, which in Dirac's notation are written just putting two kets one after another. E.g.
$$\ket{m\up} \ket{n\up} \quad \ket{m\up} \ket{n\dn} \quad \ket{m\dn} \ket{n\up} \quad \ket{m\dn} \ket{n\dn}$$
for all positive integers $m$, $n$. A shorthand may be used:
$$\ket{m\up\,;\,n\up} \  
\ket{m\up\,;\,n\dn} \ 
\ket{m\dn\,;\,n\up} \  
\ket{m\dn\,;\,n\dn} \tag2$$
where labels preceding ";" refer to first particle, those following to the second.
But states in (2) are wrong for identical fermion particles, as they
aren't antisymmetrized. The right ones are
$$\eqalign{
    &\ket{m\up\,;\,n\up} - \ket{n\up\,;\,m\up} \qquad
     \ket{m\up\,;\,n\dn} - \ket{n\dn\,;\,m\up} \cr
    &\ket{m\dn\,;\,n\up} - \ket{n\up\,;\,m\dn} \qquad
     \ket{m\dn\,;\,n\dn} - \ket{n\dn\,;\,m\dn} \cr}$$
(once again I'm neglecting normalization).
Observe however that if $m=n$ first and fourth expressions are identically zero, whereas second and third are the same apart for sign, thus representing the same state. This is the mathematical form PEP assumes in QM: for $m=n$ just one state exists for two particles, for $m\ne n$ there are four.
For more particles we would proceed analogously, with a somewhat higher complication.

Let's compute pressure
First of all let me remark that not fermions alone exert a pressure when confined in a finite volume. Bosons do as well. Radiation pressure is an example, and photons are bosons. So let's compute the pressure exerted by a gas of non-interacting bosons at $0\,$K, when all particles are in the ground state (this isn't forbidden for bosons).
If we have $N$ particles, overall energy is given by (1) taken for $n=1$ and multiplied by $N$;
$$E = {N h^2 \over 8\,m\,L^2}.$$
As we are in one dimension we'll speak of force, not of pressure. It's most easily computed by
$$F = -\PD EL = {N h^2 \over 4\,m\,L^3}.\tag3$$
For those who find too abstract the above derivation I'll add a semiclassical one. In our box we have free particles bouncing back and forth between boundaries. Their momentum is $p=h/(2L)$. A particle hits one boundary (e.g. the left one) once in a time
$${2L \over v} = {2mL \over p} = 
{4 m L^2 \over h}$$
and every time it exchanges with the boundary a momentum $2p$. Then the momentum exchanged per unit of time, i.e. the force, is
$$f = 2p\, {h \over 4 m L^2} = 
{h^2 \over 4 m L^3}.$$
This holds for one particle. It's only left to multiply by $N$ to get (3).

Now for fermions
What's the difference? Simply that even at $0\,$K a fermion gas
doesn't have all particles in ground state. We've seen why it's
forbidden by antisymmetry. So we have the task to arrange an
antisymmetrical ket for $N$ particles, which sounds prohibitive.
Actually it's not so much so, but we'll follow a roundabout way, in
principle an approximated one but absolutely adequate to our purposes.
For each $n$ there are two states allowed, spin up and spin down. We
already saw that for $m=n=1$ and two particles only one state is
possible, wheres none is possibile for three. If we accept values 1 and
2 for $m$, $n$ we can accomodate up to four particles
$$\ket{1\up;1\dn;2\up;2\dn}$$
(to be antisymmetrized). So we see that for $N$ particles all states
from 1 to $N/2$ will be occupied, each by two particles with opposite
spins.
And now we are able to compute the energy:
$$E = 2\,\sum_{n=1}^{N/2} E_n = 
      2\,\sum_{n=1}^{N/2} {n^2 h^2 \over 8\,m\,L^2} =
      {h^2 \over 4\,m\,L^2} \sum_{n=1}^{N/2} n^2$$
(the sum has to be multiplied by 2 since for every $n$ there are two
spin states). If $N$ is large we may approximate the sum to ${1 \over 24}\,N^3$ and get
$$E = {N^3 h^2 \over 96\,m\,L^2}.$$
As before
$$F = -\PD EL = {N^3 h^2 \over 48\,m\,L^3}.\tag4$$
You can see the difference between (3) and (4). Whereas for bosons
force is $\propto N$, for fermions it's $\propto N^3$, then much larger
if $N$ is large. Actually extremely larger for a white dwarf: try to
estimate how much is $N$ (number of electrons) for a star having Sun's
mass.
To be sure we should reason about pressure, not about force. This
requires leaving our naive 1D model for a more realistic 3D one. I'll
content myself to give the result
$$P = {(3\,\pi^2)}^{2/3} 
        \left(\!{\hbar^2 \over m}\!\right)\,{N \over V}^{\!5/3}.$$
The most important difference is in the dependence on $N$: $N^{5/3}$
instead of $N^3$. I can't explain its origin (it has to do with the
different accounting in 1D and in 3D for the one-particle states up to
$N/2$). I'll only say that even with the smaller exponent resulting
pressure is enough to counterbalance gravity for dwarfs of mass near
Sun's and size about Earth's.

A final comment
It should be clear that no mysterious force could account for our
results. Note that total energy of $N$ particles depends on a power of
$N$ and it would be hard to explain that with some interaction between
particles. Instead all depends on which and how many independent states
are allowed when identical particles are concerned. In a different
way for bosons against fermions and both different of the one that
would be used for classical particles.
As Feynman liked to say, this is the way things are.
A: The Pauli Exclusion Principle isn't a fundamental force because it doesn't have the same origin as the 4 fundamental forces. It's like the pressure you feel from a normal gas in that it definitely exists, but it comes from the fact that you have many particles in the system and are averaging over their behavior. We usually call that an "emergent phenomenon," which is a property we detect at the macroscopic level but looks very different at smaller scales.
One of the other answers described the Pauli Exclusion Principle at the atomic scale for a particle in a well — you can see that it isn't treated like a force in the same way that electromagnetism is. An emergent example is the pressure that keeps a white dwarf from collapsing on itself.
