We present several existence and nonexistence results for permutation binomials of the form $x^r(x^{q-1}+a)$, where $e\geq 2$ and $a\in \mathbb{F}_{q^e}^*$. As a consequence, we obtain a complete characterization of such permutation binomials over $\mathbb{F}_{q^2}$, $\mathbb{F}_{q^3}$, $\mathbb{F}_{q^4}$, $\mathbb{F}_{p^5}$, and $\mathbb{F}_{p^6}$, where $p$ is an odd prime.