Sounds a lot like the private key to decrypt this information was stored alongside the data in the database... whoops!

Not necessarily, even if this was done "properly" there is no guarantee that from the internal network there wasnt a separate exploit that the attacker could use to gain access to a different node which had the key in memory. With breakages like these you generally have to assume that anything that is theoretically possible has happened.