...how to approach storing a password in a secure way, without storing keys or passwords in the clear, and without requiring user interaction. It seems like an impossible task...

You hit the nail on the head. It is impossible (1). Since they probably don't think it's impossible, they must think that compiling a program is the same as encrypting it. It's not, just as dragonchild said above. In fact, if they think that is secure, they might be impressed if you told them that your entire application is ROT-26 encrypted.

Furthermore, even if they changed the policy so that it was possible to comply with by allowing you to store the private key in plain text, then it would still not increase the security of the credentials very much. Because then all a cracker has to do is get the plain text private key.

In other words, at some point, something has to be stored in plain text. You can encrypt it 10 times and 9 of the private keys will be encrypted, but the last one has to be plain text. That might delay a script kiddie, but I wouldn't put much stock in that defense.

The only way to keep someone from getting the credentials is plain old security. It doesn't matter if it's in the source code, binary, configuration file, or what. If a cracker gets into your system and can read the password and the private key, then it's game over.

So you have to focus on preventing crackers from getting the password file and the private key file. Good luck in dealing with this situation (ugh, and the politics).

(1) OK, actually it is possible. But you would need a Cray super computer. Because instead of storing the private key in plain text, you would have to run a brute force decryption crack program to get the contents of the encrypted passwords every time your app starts up.

Or, instead of encrypting the password, you could store it in the middle of some really bad VB code. While reading the code, the cracker would go clinically insane before he finds the password.