Taiwan IMO Selection Camp

The answer is no! We will prove below that if $(a,b)$ is "1110-sufficient", then for any $k = 37^r$, $(a,b)$ is $k$-sufficient.

(1) If $(a,b)$ is 1110-sufficient, then $(a,b)$ is 37-sufficient.
Suppose $(a,b)$ is not 37-sufficient, then there exist $x, y$ such that $37 \mid P(x) - P(y)$ but $x - y$ is not a multiple of 37. By the Chinese Remainder Theorem, there exist integers $x', y'$ such that both $x'$ and $y'$ are multiples of 30, and $37 \mid x' - x$, $37 \mid y' - y$. Thus we have $30 \mid P(x') - P(y')$ and $37 \mid P(x') - P(y')$, that is, $1110 \mid P(x') - P(y')$. Hence 1110 does not divide $x' - y'$, giving a contradiction.

(2) If $(a,b)$ is 37-sufficient, then $37 \mid a$.
By contradiction, suppose $a$ is not a multiple of 37. First, if $b$ is also not a multiple of 37, note that $P(x) - P(y) = (a(x^2 + xy + y^2) + b)(x - y)$, and $4a(x^2 + xy + y^2) + 4b = a(2x + y)^2 + 3a y^2 + 4b$. Let the sets
$$S = \{ a s^2 + b \text{ mod } 37 \mid s \text{ is an integer} \}, \quad T = \{ -3a t^2 \text{ mod } 37 \mid t \text{ is an integer} \},$$
where the residues here are all taken between 0 and 36. Then both $S$ and $T$ have 19 elements, so there must be overlap between them; that is, there exist integers $s, t$ such that $37 \mid a s^2 + 3a t^2 + b$.
Since 37 does not divide $b$, $s$ and $t$ are not both 0, so we may take $t' = t$ or $-t$, such that $3t' - s$ is not a multiple of 37. Take an integer $s'$ such that $2s' + t' \equiv s \pmod{37}$, then
$$4a(s'^2 + s' t' + t'^2) + 4b \equiv a s + 3 t^2 + b \equiv 0 \pmod{37},$$
and since $3t' - s$ is not a multiple of 37, $3t' - (2s' + t')$ is not a multiple of 37, that is, $s'$ and $t'$ have different residues mod 37. However we have $37 \mid (a(s'^2 + s' t' + t'^2) + b)(s' - t') = P(s') - P(t')$, a contradiction.
If $b$ is a multiple of 37, then $P(10) - P(1) = 999a + 9b$ is a multiple of 37, also a contradiction, so (2) is proved.

(3) For any positive integer $r$, $(a, b)$ is $37^r$-sufficient.
By (2), $37 \mid a$. Clearly $b$ cannot be a multiple of 37, otherwise $37 \mid P(1) - P(0)$, a contradiction. For any integers $x, y$, if $37^r \mid P(x) - P(y) = (a(x^2 + xy + y^2) + b)(x - y)$, then note that $a(x^2 + xy + y^2) + b \equiv b \pmod{37}$ is not a multiple of 37, hence $37^r \mid x - y$, which completes the proof.