Is Velocity Really a Vector?

It boils down to this:

A Galilean transformation is only defined as a transformation of position vectors:

$$ x'(t) = x(t) - vt $$

From this we can derive how time derivatives of position transform:

$$ u'(t) = \frac{d}{dt} x'(t) = \frac{d}{dt}x(t) - v = u(t) - v $$

$$ a'(t) = \frac{d}{dt} u'(t) = \frac{d}{dt}u(t) - 0 = a(t) $$

Then assume mass is Galilean invariant and define the force vector by Newton's second law. We get:

$$ F'(t) = m'a'(t) = ma(t) = F(t) $$

First of all, speaking of a vector in nonrelativistic physics, one usually refers to the properties of the given quantity under spatial rotations only. That is, a vector is defined as a certain representation of the rotation group.

That said, however, the use of the term vector clearly is just a matter of convention. Why vectors in nonrelativistic and relativistic physics are treated differently is to some extent a matter of sociology, but there can also be more concrete reasons for doing so.

First, the philosophy whereby physical laws are derived from their symmetries, and not vice versa, was historically only introduced along with relativity, hence the focus on manifest Lorentz invariance in relativity. Second, it is a mathematical fact that the classification of representations of the Galilei group is much more tricky than the same problem for the Lorentz group (the reason being that the Galilei group is not semisimple). See for instance this paper: the Galilei group has not only 3-vectors, but also two different types of 4-vectors, and 5-vectors, among others. The construction of invariants for a given representation is likewise a nontrivial task. I believe this is the main practical reason why representations of the Galilei group and their use are much less frequently discussed than those of the Lorentz group.

To answer the original question, velocity is a vector under rotations. But under Galilei transformations, velocity is just a part of a 5-vector.