Since the users aren't able to choose their password, the passwords should be generated randomly. If the passwords are generated using some algorithm, as you stated, once the algorithm is cracked, all of the passwords can be cracked.
If you must store retrievable passwords, you should still encrypt and salt them. See adobe's recent issue where 150 million of adobe's encrypted passwords were leaked. The problem with unsalted passwords is that even if I can't crack the encryption, I can still see everybody who has the same password as me.
Admin Retrieval
For admin-only retrieval of passwords, you could use a password vault system, where one password entered by a staff member unlocks access to additional stored passwords. Ideally, you should have a system where you can select and display a single password on the screen. It should encrypt the passwords, log accesses, and be controlled by an administrator.
This could be a web-based system, but hosted internally on an intranet, perhaps accessed through a VPN. RDP or something similar may also be viable, perhaps even using two-factor authentication.
Unfortunately, we don't recommend products on StackOverflow.
End User Retrieval
We've designed a system in the past where you can recover a password via a HTTPS secured web site. You simply enter your username, and a random one-time-use retrieval code is delivered to the email address on record.
While we're not in control of the security level on their email account, we at least assume that only the user knows the password to access the email account. This forces the user to re-authenticate in some form in order to retrieve their password.
They then type the retrieval code into a web form and are shown their password. Again, this web site is secured with HTTPS. Additionally, the user must keep the web page open during the transaction (secure session), and the IP address must not change during the transaction.