The only alternative that I can think of is that one of the two other users' machines was compromised, but AFAIK I didn't give them root access. Plus, the logs show an extreme number of login attempts (tens of thousands of entries in auth.log) with an eventually successful root login.
Any other ideas of what might've been an alternative cause?
Maybe you’re right though.
EDIT: to be clear, I am pretty sure was the only person who used the root password to log in, and the single other user used a similarly long and random password with a different username. if I'd been compromised my problems would be quite a bit bigger. All I know is that right before the 'fatal' root login, there are 40.000+ lines of login attempts from ip's that originated from shady places (at least based on entering them in various GeoIP sites).
I suppose even minimal extra security would've helped (no root user, only allow x login attempts in y time, changing the port for ssh), but I was still surprised someone got in so soon by simply guessing a 20+ string of gibberish (I still wonder if maybe something else happened).
All that said, I've had servers running for years without any successful hack, and in all those cases using ssh keys instead of password logins probably made all the difference.