The title of the article should really be changed to "How we cracked millions of Ashley Madison passwords by bypassing their strong bcrypt hashes because they thought they were clever" but that's less clickbaity Also, never ever roll your own encryption - it will be flawed (unless you employ at least 3 crypto experts and get it peer reviewed - and even then it's probably still flawed).
They didn't really roll their own encryption right? They rolled their own session login stuff, used it for some sort of login-key (what I assume they passed with server sessions). Why they would do that instead of a simple session ID I will probably never know. Maybe they did it so they could have independent backends (instead of having to share session keys across load balanced api servers).
Since at some point the loginkey was based on the unencrypted password that means that they either had to store the PW in clear (and fetch them from the DB) or generate the key at account creation and fetch it from the DB anyway.
A good strategy to check the token validity without reaching the DB is to sign it cryptographically. The loginKey can be $randomString+sign($randomString). The endpoint can check the signature before doing more costly things like a network request.