As the title suggests, the problem here is:
Find all functions $f:\mathbb{Z}\to\mathbb{N}$ such that, for every $x,y\in\mathbb{Z}$, we have $$\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$$
I have already solved the problem - but, with seven pages full of calculations and case splitting, not quite the elegant proof I wished I'd have. I've put the answer in the yellow box below (I've hidden it for the people that wish to try this themselves first). Hover your mouse over the box to reveal its contents.
The only solution is $f(x)=1$ for all $x\in\mathbb{Z}$.
I'd love to see a shorter proof for this. I'd be happy with any suggestions!
For any $a, b > 0$, $x=a, y=-b$ gives $\max(f(a+b), f(a-b)) | \min(af(-b)+bf(a), -ab)$. Since $f$ takes positive values, $\max(f(a + b), f(a-b)) | ab$.
For $a=b=1$ this shows that $f(0)=f(2)=1$.
For $a=b$ this shows that $f(2a) | a^2$, and for $b=1$ this shows that $\max(f(a+1), f(a-1))|a$. Combined together these imply that $f(x) = 1$ for all even $x \geq 0$.
Now we claim that either $f(1) = 1$ or $f(3) = 1$. Suppose that neither equalled one. By the above inequality with $a=2$ and $b=1$, $\max(f(1), f(3)) | 2$, so $f(1)=f(3)=2$. By the original inequality with $x=3$ and $y=2$, $\max(f(1), f(5)) = \min(3f(2)-2f(3), 6)$. Since $3f(2)-2f(3) = 3 \cdot 1 - 2 \cdot 2 = -1$, $f(1)=1$, a contradiction. Therefore either $f(1) = 1$ or $f(3) = 1$.
Now for any odd $x \geq 1$ with $f(x) = 1$ let $m = \max(f(x+2), f(x-2))$. By the original inequality $m| \min(xf(2)-2f(x), 2x) =x-2$. If $x=1$ then this shows that $m=1$. Otherwise, if $x > 1$, by the above inequality ($a=x, b=2$) $m | 2x$, so since $\gcd(x-2, 2x) = 1$, $m = 1$. Either way $f(x \pm 2) = 1$, so by induction $f(x) = 1$ for all odd $x > 0$.
Therefore $f(x) = 1$ for all integer $x \geq 0$.
Now consider the case of negative arguments to $f$. For $x > 0$ and any $k > 0$, use the above inequality with $a = kx$ and $b = (k+1)x$. We know that $f((2k+1)x) = 1$, so the above inequality shows that $f(a-b) = f(-x) | k(k+1)x^2$. Since this holds for all such $k$, $f(-x) | x^2$.
In particular this shows that $f(-1) = 1$.
For $x > 0$, the above inequality with $a = 1$ and $b=x$ yields $\max(f(1+x), f(1-x)) = f(1-x) | x$. So for $x > 1$, $f(-x) | x + 1$. We also know $f(-x) | x^2$, so since $\gcd(x^2, x + 1) = 1$, $f(-x) = 1$.
Thus $f(x)=1$ for all $x \in \mathbb{Z}$. QED