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).