You are correct if the system you are connecting to can accept nothing but a password as a credential. If this is how the remote system works, it is unfortunately designed, and should be extended if possible to accept some other kind of token. Examples of more appropriate tokens are Kerberos tickets, SSH keys, OpenID credentials, or other custom per-application credentials.
All of the good authentication solutions have something in common: They allow the user to authorize you to connect on their behalf, without having to give you their credentials. A good system allows my administrative assistant to buy airplane tickets on my behalf. It doesn't require my admin to impersonate me.
If however, the remote systems are poorly designed and cannot accept this kind of delegated credential, then you have no choice but to store the passwords. It is traditional in that case to obfuscate the password in your database using some kind of "encryption key and algorithm." (For example, AES encrypting the passwords against a key stored on disk.) This should not be confused with real encryption; it is only obfuscation. But it can be useful obfuscation if you have no other choices.
A better solution than a single password stored on disk is a hardware key that performs the decryption for you. Such a device is often called a Hardware Security Module and often takes the form of a smartcard (sometimes it's a full rack-mounted device, a board, or a USB key). You present the encrypted password to the HSM, and it hands you back the unencrypted password. The advantage of this approach is that if someone clones your disk, they still cannot decrypt the passwords. HSMs are difficult to physically clone, making it much harder for an attacker to steal the credentials without being detected. In the best designs, the process that talks to the HSM has a credential that is hand-entered at boot and is only stored in memory. So random processes cannot query the HSM, and if the machine is unplugged it can no longer access the passwords. Even in this scenario, it is possible that the attacker might trick the system into decrypting all the passwords for him, but the attack surface is greatly diminished.