All they had to do was make showing ads part of the ToS
for developing third party apps,
It seems like such an obvious solution to me, but I haven't seen it mentioned.
One possible shortcoming (from Reddit's perspective) is the fact that the official Reddit app doesn't just show ads, it also collects all sorts of other user behavior data. So for them it might be able more than simply showing ads.
That's just a wild guess on my part, though.