I am not able to replicate on a clean 1.2 install.
I have an admin user and a regular user, both with "Allow others to see when I am online" disabled. I have allowed guests to search users and view directory.
Admin can see online status of both users, regular user can see neither, guests can see neither. As expected.
Can you check "Always view user last seen time" permission is only given to moderators/admins? And that you are testing with a user who doesn't have that privilege?
Do you also see the user online badge on their profile and next to their usernames in posts or only in the user directory? The same code controls both so there shouldn't be any difference.