Take the two events when the muon is created, and when it decays. We'll choose the origins of the muon rest frame and the lab rest frame so their origins coincide at the point and time the muon is created i.e. the muon is created at (0, 0) in both frames. Both frames will agree about their relative velocity $v$.
In the muon's rest frame it is stationary, so it is created at $(0, 0)$ and decays at $(t_\mu, 0)$, where $t_\mu$ is the muon lifetime (about 2.2$\mu$s).
Now work out what happens in the lab. We've agreed the muon is created at $(0, 0)$ in both frames, so we just have to work out where the spacetime point $(t_\mu, 0)$ is in lab co-ordinates. Once we do that we'll have the lifetime of the muon as seen in the lab.
The only safe way to do this (especially for beginners in SR) is to use the Lorentz transformations, which are:
$$ t' = \gamma \left( t - \frac{vx}{c^2}\right) $$
$$ x' = \gamma \left( x- vt \right) $$
So the point $(t, x) = (t_\mu, 0)$ transforms to $(t', x') = (\gamma t_\mu, -\gamma vt_\mu)$. The lifetime of the muon in the lab frame is $\gamma t_\mu$, and in that time it manages to travel a distance $\gamma v t_\mu$: a result that is reassuring because it's just the velocity in the lab frame times the lifetime in the lab frame.
The trouble is that you're trying to use hand waving arguments, and these are usually a minefield for the beginner because there are so many conceptual issues with SR. If you're trying to work through an apparent paradox in SR the only safe way to procede is to identify the key spacetime points and work out how they transform between frames.
Response to comment:
I didn't address your question about the relative rate clocks run because it isn't a helpful concept. Let me try an illustrate this by addressing your question about the muon. You are correct that the lab sees the muon clock run slow and the muon sees the lab clock run slow. I'm guessing (comment if I'm wrong) that you are puzzled because the situation is apparently symmetrical but the muon lifetime is different in the two frames. How can the apparent symmetry in clock rates produce an asymmetrical result?
The reason for the asymmetry gets at the heart of SR, so actually you've asked an excellent question. The reason for the asymmetry is that in the muon rest frame the creation and decay take place at the same place, $x = 0$, but in the lab frame they take place in different places: creation at $x = 0$ and decay at $x = \gamma vt_\mu$. It's the asymmetry in the position that is related to the asymmetry in time.
To see how this works you need to understand that the fundamental basis of SR is an invariance called the line element (also known as the proper time). Suppose you have two spacetime points $(t, x, y, z)$ and $(t+dt, x+dx, y+dy, z+dz)$ then the line element is defined by:
$$ ds^2 = -c^2dt^2 + dx^2 + dy^2 + dz^2 $$
This should remind you of Pythagorus' theorem for the distance between two points in space, and indeed that's exactly the role it plays in SR. It is the spacetime distance between the two spacetime points. However you should note that unlike Pythagorus' theorem the $dt^2$ has a minus sign, and it's this minus sign that is responsible for all the weird effects in SR.
The key point in SR (and GR in fact) is that the quantity $ds^2$ is an invariant i.e. all observers in all frames will agree it has the same value.
Let's see how this applies to the muon. We can ignore $dy$ and $dz$ because we'll take the muon to be travelling along the $x$ axis, so $ds^2 = -c^2dt^2 + dx^2$. First calculate $ds^2$ between the muon creation and decay in the muon rest frame. Because in its rest frame the muon is stationary $ds^2 = -c^2dt^2$, so for the muon in its rest frame:
$$ ds^2 = -c^2t_\mu^2 $$
So if we calculate $ds^2$ in the lab frame we should also find it's $-c^2t_\mu^2$, and I'll show this in a moment, but first I want to point out the underlying principles.
I've said $ds^2$ has to be invariant, and that means I can add zero to it because adding zero doesn't change it's value. This may seem a silly thing to say, but suppose we take a change in time and $x$ such that:
$$ ds_1^2 = -c^2dt_1^2 + dx_1^2 = 0 $$
i.e. we choose $dt_1$ and $dx_1$ so that when you calculate the line element $ds_1^2$ comes out zero. If $ds_1^2$ is zero I can add it to my line element $ds^2$ that I calculated above without changing its value. And this is the key point: I can add some $dx_1$ to the spacing between the spacetime points provided I add a corresponding $dt_1$ that ensures the net change in $ds^2$ is zero. This is exactly what happens in the lab frame. The $x$ spacing has changed because the creation and decay no longer happen in the same place, and to balance this the $t$ spacing has to change to keep $ds^2$ constant. This is the origin of time dilation. It's not really clocks running at different rates, it's that different observers will disagree about the $x$ and $t$ spacing of the events.
It just remains to prove that $ds^2$ really is constant in the muon experiment. In the lab frame the two events are $(0, 0)$ and $(\gamma t_\mu, -\gamma vt_\mu)$ so $ds^2$ is given by:
$$ \begin{split}
ds^2 &= -c^2\gamma^2t_\mu^2 + \gamma^2v^2t_\mu^2 \\
&= \gamma^2 t_\mu^2 (v^2 - c^2) \\
&= \frac{v^2 - c^2}{1 - v^2/c^2} t_\mu^2 \\
&= \frac{v^2 - c^2}{c^2 - v^2} c^2 t_\mu^2 \\
&= -c^2t_\mu^2
\end{split} $$
and this is the same value we got in the muon rest frame. QED!
