  We introduce uniformly vertex-transitive graphs as vertex-transitive graphs
satisfying a stronger condition on their automorphism groups, motivated by a
problem which arises from a Sinkhorn-type algorithm. We use the derangement
graph $D(\Gamma)$ of a given graph $\Gamma$ to show that the uniform
vertex-transitivity of $\Gamma$ is equivalent to the existence of cliques of
sufficient size in $D(\Gamma)$. Using this method, we find examples of graphs
that are vertex-transitive but not uniformly vertex-transitive, settling a
previously open question. Furthermore, we develop sufficient criteria for
uniform vertex-transitivity in the situation of a graph with an imprimitive
automorphism group. We classify the non-Cayley uniformly vertex-transitive
graphs on less than 30 vertices outside of two complementary pairs of graphs.
