I cannot figure out how for the life of me that I am supposed to take an existing contact and mark them for Mail for Exhange

I only get that option when adding a contact. After that, it looks like you are out of luck.