It is not hopeless to extend this argument so that it applies to all finite groups of odd prime power order. Let $p$ be an odd prime, and let $K$ be a $p$-group. The congruence $|K| \equiv c(K) \mod{16}$ can be proven as a consequence of the stronger (when $p > 3$) congruence $|K| \equiv c(K) \mod{(p^{2}-1)(p-1)}$. This congruence is the best possible in the sense that there are $p$-groups (nonabelian groups of order $p^{3}$) for which $|K| - c(K) = (p^{2}-1)(p-1)$.
Let the exponent of $K$ be $p^{k}$, and let $L$ be the nilpotence class of $K$. It is difficult to work with $B(2,p^{k})$ or $Aut(B(2,p^{k}))$ when $p^{k} > 3 $ and neither of those groups is known to be finite, or, worse, when $p^{k} \geq 673$ and they are known to be infinite.
Instead, we build from $K$ the group
$P = < x,y| w^{p^{k}}=1, [w_{1}, \ldots , w_{L+1}]=1 >$,
where $w, w_{1}, \ldots , w_{L+1}$ range independently over every possible word in the generators.
Claim. $P$ is finite.
Proof of Claim. We regard $k$ as fixed and proceed by induction on $L$. When $L = 1$, $P$ is abelian and generated by two elements of order dividing $p^{k}$ so $|P| \leq p^{2k}$ and the base case is proved.
If $L > 1$, it suffices to prove that the group $P_{L}$ in the descending central series of $P$ is finitely generated, since it is abelian and all its elements have finite order dividing $p^{k}$. Then every $(L-1)$-fold commutator $[w_{1}, \ldots , w_{L}]$ is central so $P/P_{L}$ is a quotient of the group which has the same definition as $P$, except for the replacement of $L$ by $L-1$. Since that group is finite by induction, $P/P_{L}$ is finite and the finiteness of $P_{L}$ implies the finiteness of $P$. To prove this, we use the
Commutator Lemma. If $G = < g_{1}, \ldots , g_{m} >$ and $H = < h_{1}, \ldots , h_{r} > \leq G$ for some positive integers $m$ and $r$, then the commutator subgroup $[G,H]$ has a generating set consisting of iterated commutators $[e_{1}, \ldots , e_{C}]$, where each $e_{i} \in $ {$g_{1}^{\pm 1}, \ldots , g_{m}^{\pm 1}, h_{1}^{\pm 1}, \ldots , h_{r}^{\pm 1}$}.
Proof of Commutator Lemma.
Recall the commutator identities $[t, uv] = [t,v][t,u][t,u,v]$ and $[tu, v] = [t,v][t,v,u][u,v]$.
An arbitrary element of $[G,H]$ is a product of commutators of the form $[g,h]$, where $g = \gamma_{1} \ldots \gamma_{s_{1}}$, $h = \eta_{1} \ldots \eta_{s_{2}}$, each $\gamma_{i} \in$ {$g_{1}^{\pm 1}, \ldots , g_{m}^{\pm 1}$} and each $\eta_{i} \in$ {$h_{1}^{\pm 1}, \ldots , h_{r}^{\pm 1}$}. We prove it for commutators of this form by reducing the length of $h$ and then reducing the length of $g$ as follows:
If $s_{2} > 1$,
$[g, \eta_{1} \ldots \eta_{s_{2}}] = [g, \eta_{2} \ldots \eta_{s_{2}}][g, \eta_{1}][g, \eta_{1}, \eta_{2} \ldots \eta_{s_{2}}]$.
If $s_{2} = 1$ and $s_{1} > 1$,
$[\gamma_{1} \ldots \gamma_{s_{1}}, \eta_{1}] = [\gamma_{1}, \eta_{1}][\gamma_{1}, \eta_{1}, \gamma_{2} \ldots \gamma_{s_{1}}][\gamma_{2} \ldots \gamma_{s_{1}}, \eta_{1}]$.
The middle factor on the right hand side can be written as a product of commutators of the desired form by repeatedly applying the equation cited for handling the $s_{2} > 1$ case. Then the final factor has the length of $g$ reduced by 1, as desired. The Commutator Lemma is now proven.
Then $[P,P]$ is generated by a set of such iterated commutators involving $x$, $y$, $x^{-1}$ and $y^{-1}$. Since these have at most $L$ arguments, this gives a generating set of at most $\frac{4^{L+1} - 16}{3}$ elements for $[G,G]$. Then, if one has a $\rho$-element generating set for the subgroup $P_{i}$ in the descending central series of $G$, the Commutator Lemma gives a generating set for $P_{i+1}$ consisting of at most $\frac{(2\rho + 2)^{L+1} - (2\rho + 2)^{2}}{2\rho + 1}$ elements (these finite geometric series arise from summing over the possible lengths of such commutators). Then, continuing in this way, all of the subgroups in the descending central series for $P$ are finitely generated, and the finiteness of $P$ is proven.
Here $\Phi$ denotes the Frattini subgroup.
Denote $|P|$ by $p^{E}$. Let $W_{1}(x,y)$ and $W_{2}(x,y)$ be elements of $P$, considered as words in $x$ and $y$ (well-defined up to the relations). Any substitution $(x,y) \to (W_{1}(x,y),W_{2}(x,y))$ turns relations into other relations (due to the way the relations defining $P$ involve all possible words), so any such substitution defines an endomorphism of $P$. Such a substitution defines an automorphism of $P$ if and only if it is invertible. Since $P$ is finite, an endomorphism from $P$ to itself is invertible if and only if it is surjective. If an endomorphism $\psi$ of $P$ is not surjective, then $\psi(P)$ is contained in some maximal subgroup of $P$ and $\psi(P)\Phi(P)/\Phi(P)$ is a subspace of $P/\Phi(P)$ of positive $\mathbb{Z}/(p)$-codimension. So the endomorphism $\psi$ of $P$ is an automorphism if and only if its action on $P/\Phi(P)$ is via an element of $GL(2,\mathbb{Z}/(p))$. This means that the proportion of endomorphisms of $P$ which are automorphisms is the proportion of 2x2 matrices over $\mathbb{Z}/(p)$ which are invertible. Therefore, we obtain the result that $|Aut(P)| = p^{2E-3}(p^{2}-1)(p-1)$.
Now we let $Aut(P)$ act on the set of non-commuting pairs of elements of $K$. This is well-defined since the relations that hold in $P$ also hold in $K$, and in the subgroup of $K$ generated by two non-commuting elements. To get information about the size of an orbit of a non-commuting pair under this action, it suffices to get information about the order of the stabilizer in $Aut(P)$.
If $a,b \in K$ form a non-commuting pair such that $a = W_{1}(a,b)$ and $b = W_{2}(a,b)$, then $1 = a^{-1}W_{1}(a,b) = b^{-1}W_{2}(a,b)$. $| < a,b > /\Phi(< a,b >)| = p^{2}$, since $< a,b >$ is noncyclic ($< a,b >$ is nonabelian since $(a,b)$ is a non-commuting pair) and generated by 2 elements. This means that, passing to $< a,b >/\Phi(< a,b >)$, we see that $(a,b) \to (W_{1}(a,b),W_{2}(a,b))$ is mapped to the identity matrix in $GL(2,\mathbb{Z}/(p))$. Then likewise, in $Aut(P)$, $(x,y) \to (W_{1}(x,y),W_{2}(x,y))$ must be in the subgroup of order $p^{2E-4}$ which is the kernel of the homomorphism from $Aut(P)$ to $GL(2,\mathbb{Z}/(p))$. Therefore any orbit for the action of $Aut(P)$ on the set of non-commuting pairs of elements of $K$ has size equal to a multiple of $(p^{2}-1)(p^{2}-p)$, and therefore $(p^{2}-1)(p^{2}-p)$ divides $|K|(|K| - c(K))$. Since $|K|$ is a power of $p$, we obtain the congruence $|K| \equiv c(K) \mod{(p^{2}-1)(p-1)}$ as claimed.
