Special Relativity states that as an object increases in velocity, it gets more dense (mass increases, volume shrinks).
No, no, no. Absolutely not.
But I know why you think this. Back many decades ago, before I was born, lots of physicists wrote physics papers and textbooks without really understanding relativity. They made mistakes. Not necessarily errors, but certainly pedagogical mistakes. And these mistakes have proven most insidious and hard to weed out. The most egregious of these is stating that mass increases with velocity.
As understood today by any and all who deal with relativity, objects have an invariant rest mass $m$. This is the same for all observers. As a Lorentz scalar, it does not change when going into different frames of reference.
Old papers -- and remember, we're talking the early to middle 20th century, when no one know what DNA was, computers didn't exist, and we hadn't even coined the term "Big Bang" -- would refer to the combined quantity $\gamma m$ as relativistic mass. Sometimes they would write it as just $m$, where my rest mass above was written $m_0$: $m = \gamma m_0$.
It is this second $m$, this "relativistic mass," that changes with an object's relative velocity. The true $m$, denoted $m_0$ back in the dark ages, never changes.
An object undergoing a decrease in velocity would begin to diffuse (mass decreases, volume inflates).
Even if we agree we're talking about $\gamma m$ decreasing, there is a lower limit. The factor $\gamma$ is given by $1/\sqrt{1-v^2}$, where $v$ is the relative velocity between reference frames. You can check for yourself that for any $v$ bounded by the speed of light, $-c < v < c$, we have $\gamma \geq 1$. The minimum value of $\gamma m$ is $m$, and it occurs when $\gamma = 1$, i.e. when you the observer are comoving with the object, i.e. when the object appears to be at rest. Even the accursed relativistic mass can't go to $0$.
How much would some sum over $\gamma m$ for all objects change if they stopped moving from our point of view? Not much, actually. For cosmological purposes, ordinary matter is modeled very well by what cosmologists call dust. Basically, this makes the approximation that $\gamma \approx 1$, because most matter really is moving slow compared to the speed of light: $v \ll c$.
Note that I'm only talking about peculiar motion here -- the motion in addition to the uniform expansion of the universe. This is because the apparent "velocities" with which galaxies are receding can't really be analyzed in the same special relativistic framework. (For one, recession velocities are often greater than $c$!)