Meeting Bellegar again near the passage north into the Maxos temple area must be done before getting the battle tower. The meeting will leave you on the ledge to Needleman's storage, but the only thing you can do then is loot the chest outside, and maybe a couple of the bodies.
After that, returning to the fortune teller will earn you an achievement.
Needleman can be found somewhere prominent above the poison gas, and (without his helmet on) can be mindread for the password.
He is on the top level of Lovis' tower, where you could have gotten earlier by one of Bellegar's teleporters, and looted a chest. After getting the battle tower the chest is no longer accessible.
