With shell providers, you can't really bind to localhost .. that's true. However those same users also share the same interface and have just as much access to it as you would. Meaning they can sniff the IPs on it.
IRC software was never really intended to be on shared resources, such as shell providers as it's commonly practiced today. In the event that you cannot use localhost, then the next best solution is to use stunnel for secured data transferance. Another even easier and less resource intensive solution is to use MD5 encrypted passwords and forego the usage of GETPASS and SENDPASS. SA"s can use saset in order to change a users password. Other than passwords, there is no other data that is would be sensitive enough to be of use if data is sniffed/intercepted. Yes, this adds a little workload to your staff but well worth it since you are not sending passwords in plain text over the internet regardless of the box's setup.
In short, if you can't use localhost, use MD5 encrypted passwords since it doesn't use as much resources as any other form of data encryption .. including ssl even with zip.
For those that are about to ask how you insure you set a password for the right person, you simply ask them for the email address nickserv has on file, send a quick email to that address containing completely unrelated contents, then have them paste the body of the email back to you in private message.