I believe this has nothing to do with whether or not these men had ears that could hear. The Devas are able to communicate via reading and projecting thought.
The problem teaching Dhamma in the higher spheres has more to do with the fact that there is no painful sensation experienced there and apparently no memory of past lives such as could provide the understanding of pain as experienced personally.
The Buddha and other bhikkhus do manage to visit some of the lower higher realms such as the Brahma Lokas, so there must be some further explanation.
I suggest without personal experinence that I can recollect that this has to do with the enormous length of life in these spheres. The arahant that lived outside Time could visit (via a wormhole?) these higher realms, but once manifested there, if even for so short a time as it takes to snap the fingers, his return would occur millinia later. It would spoil the Buddha's mission.