DrLecter is right.
It all boils down to making sure to use the right public key. In fact this is the same for any public key cryptosystem be it RSA elGamal or ECC variants thereof.
A MAC or whatever other construction local to your system won't do the job. The MAC e.g. can only make sure the last "editor" of the message knew the symmetric key the message is enciphered with, which a man in the middle obviously always does.
You can only achieve some protection by
trusting a CA who signed the key or
trusting a PGP style "web of trust" or
by meeting your communication partner in person and exchange keys face to face.
A somewhat weaker protection independent of an external organization might be achieved by:
Using a second independent and well protected channel to transfer the public key. E.g. use the phone if you trust your mobile...
Posting a video where you read your public key aloud.
(This helps with people who know you well in person and is hard to fake - I do that with my Academic Signature ECC-key here: http://www.fh-wedel.de/~an/crypto/key_read_anders.ogv . It might be awkward with elGamal or RSA keys which need to be very long nowadays.
There are also cryptographic concepts of deterministically deriving a public key from an e-mail address or a name string. This concept is called "Identity Based Encryption" (IBE). You can find it explained in wikipedia. IBE, however, IMHO just transfers the problem and doesn't solve it.