Requirements

List of the requirements I have in mind. By importance:

• available for Android.
• no airtime minute use. This application must rely on data transfer only, especially to not cause any additional costs in usage across national borders.
• wi-fi and mobile data connection options. The application must be able to use mobile data (whatever is available: GPRS / EDGE / 3G / HSDPA / LTE) to be usable everywhere, but also must be able to use wi-fi, to reduce costs and mobile data consumption when possible.
• reliable delivery. That means, without voice loss and stuttering, even with difficult and intermittent network coverage. This implies automatic re-transmission until a voice message is successfully transmitted.
• record-and-send mode. This mode is sufficient for semi-synchronous communication in instant messenger style, and more synchronicity is only needed in time-critical uses like on construction sites, festivals etc.. Record-and-send mode makes it possible to have reliable communication and intact messages even with difficult and intermittent network coverage. If there's an optional real-time transmission mode, this is a plus but not needed.
• fast delivery. This implies automatic voice codec switching to adapt to low-bandwidth situations and intermittent network coverage.
• optionally using the internal speaker for playback. This is a good idea to protect the sender's privacy when listening to messages in crowded spaces.
• free and open source software. Very important, but not indispensable if there is really no free solution for this.
• content encryption during transmission. Important, but not indispensable.
• text messaging integration. Great to have when one cannot talk for privacy reasons or because of being in a silent environment.
• desktop interoperability. It would be great to not be tied to the phone when working at the PC. But, this is optional. Apps which are not available as browser or desktop versions can normally be run on a PC in a VirtualBox VM using Android-x86 [instructions] or alternatively can be used from within your browser using the Manymo Android emulator. Manymo allows to install your own apps here, but be aware that you need to get APK packages for them first, you can't directly install from Google Play. Also, an emulator will go to suspend mode after 10 minutes of inactivity, so it's not a really great solution.
• XMPP compatible. I'm using XMPP as my standard chat protocol now (and it is the official standard!), and it would be nice if the PTT application could integrate with this.
• photo and video messaging integration. Optional, just nice to have.
• gratis. If it can't be free, we want it at least gratis, right? 🙂

Results

This list contains, to my knowledge, all apps with PTT functionality that were available as of 2012-07-15 (additions welcome!).

Tested and recommended: (starting with the most recommendable one according to my subjective evaluation)

1. MiTalk Messenger. (Version of 3.1.435, 7.95 MiB) Really nice, as chat allows not just text and voice with its PTT button, but also "rich emoticons, photos, voice, location share, handwriting and graffiti, and more". Esp. the handwriting and drawing modes seem to be expressive and playful options. Also great, according to my tests: its tidy interface, gives feedback about message reception, notifies when the own Internet connection gets lost, notifications about messages received while offline (either as push notifications when enabled, or else when starting the app again and not being right in the chat to which the message belongs), quick transmission of voice messages, blue point icon for new messages in the thread, mode for using the earphone rather than loudspeaker for PTT messages, option to delete messages individually, and messages will only play at once if the screen is not locked and else cause a configurable message notification. The drawbacks, in this version: gratis but not free; the non-Chinese language versions are not in perfect shape; it's a Chinese manufacturer and they store the messages for (at least) forwarding them and there's no word about encryption and a rather lax policy about handing out your personal data, so better do not use it for any kind of sensitive data; the e-mail notification feature does not recognize that the notification is done; on older phones / Android versions (like the one of HTC Magic), the background mode does not work, so you will only appear as online when the application is shown in the foreground (seems because this uses push notifications, as mentioned in the config section, which might not be available in older Android versions. Also, one cannot send video (yet). And, when trying to install this version on Buildroid 4.0.4 RC1.1 with houdini, I failed to get it working; it should be tried again later [background].
2. Zello Walkie Talkie. Clear and simple interface. No ads. It tries to automatically re-connect when network connectivity becomes available again. Includes an offline voice message history.  And, there's also a iPhone, Blackberry and PC client software. The flaws in the 2012-07-14 version: not free and open; sometimes loses messages and parts of it (this can probably be fixed by using the TCP config option instead of UDP); the only way to prohibit it from playing the messages aloud immediately is setting yourself to "not available"; missed message counter is always "1" even if there are more; and there's no way to reliably determine what the last unheard message is without hearing it.

Tested and not recommended as of 2012-07-21:

1. WhatsApp. (Version 2.8.1504, 6.4 MiB) Allows to communicate with "messages, pictures, audio notes, and video messages". That's nice and it works well, but it's no true PTT app: it needs 6 or more clicks to send a voice message, which is handled like an attachment, rather than sending it with one touch-hold-release click in PTT style. Gratis for the first year, then 0.99 USD per year (though that is reportedly not enforced). Installation note: It might seem to be stuck with an "Initializing …" screen after choosing a screen name, but it just takes long to look for existing WhatsApp users if your addressbook is large (for example, 10 min for 900 contacts).
2. KakaoTalk. Includes integrated voice and text messaging, both one-on-one and in groups. This is very similar to LINE, see there. In contrast to LINE, voice message transmission is reasonably fast. However, it needs five clicks and some waiting time to send each single voice message, compared to one click (hold and release) for most PTT messengers. Also, has no mode to use the handset's earphone instead of the loudspeaker. For these reasons, not recommended. Also comes with a teenie-style emoticon set and an in-app store for more emoticons, which could be considered a nuisance.
3. Palringo. Allows voice and text messaging, and seemingly also to users of other services like XMPP [source]. It is however more centered around pre-existing chat groups rather than on one-on-one communication.
4. pttdroid. The great thing is, it is open source. However, it's a very simple app and specialized on multicast and broadcast transmission in WLAN / LAN networks. It claims that one-on-one connections are possible via 3G, but I could not find how.
5. LINE. (vesion 2.5.3, 11.4 MiB) Includes a chat with a PTT button (select "+ -> Audio Message" to get it) and also the option to send text, video and photo messages in the same chat. Look and feel and features are so much the same that this and KakaoTalk can be considered clones. Gratis but not free. It even comes with a desktop client, but that works only for Windows and OS X [source] but there's also a browser version that might (!) be usable on Linux and of course you can run it in a virtual machine like VirtualBox under Linux. Also includes SIP VoIP calls. See the manufacturer website. Test results: In my tests, the app behaved quite sluggish, taking 15-20 s to transmit a 4 s audio message (from stop of recording to start of playback). Maybe a codec issue? In any way, this seems inapt for dialogue-style talking. Also, the emoticon set is quite … Asian, so not everybody's style.
6. Virtual Walkie Talkie. Not tested.
7. smart talkie (beta). Not tested.
8. HipVoice. This is XMPP compatible, which is great [source]. However it's meant for business customers, which means that pricing starts at 10 USD monthly [source].
9. mumble-android. Not tested. The start of a Mumble client for Android. This would be very cool to have, as Mumble is open source, comes with exceptional voice quality and voice encryption by default. However neither this particular software nor its forks are currently in active development because of some technical hurdles [source]. Also, while Mumble has a "push to talk" feature, it is not clear to me so far if its audio reception is not rather full-time on. That however would be too much for mobile data rates.
10. Mangler. Not tested. A Ventrilo 3.x client for Android and thus a good replacement for the yet non-functional Android Mumble client. This client is open source, which is great, however the Ventrilo server is closed source (though gratis in a limited-capacity version). Mangler has PTT functionality [source], but as an audiospace type software, audio arrives as a continuous stream and not as messages. So, not usable in this context. And there is also Ventriloid, another open source Ventrilo client for Android that is based on Mangler.

Remaining to be tested:

1. HeyTell. This is a freemium app. In widespread use and often recommended.
2. TalkBox. Voice and text messaging. Also included photo sharing, conversation history, group chat and sharing to social networks.
3. WeChat. Provides voice and text chat with multimedia elements. Frequently used application, Chinese manufacturer … .
4. imo instant messenger. A gratis (though not open source) multi-protocol instant messenger, so interoperable with desktop applications. Though it is not clear if and how that also includes its voice instant messages. Also integrates group messaging, text messaging, video and photo sharing.
5. TT Talk. The application integrates voice and text messaging seamlessly.
6. Android Walkie-Talkie. This is one of the rare open source PTT apps, but not in development since 2009.
7. VoxNotes Push To Talk. There is a commercial service behind, but that might be only to purchase credits for sending voice messages to any normal phone.
8. coco voice. Comes with also integrated text and image messaging and optional posting to Facebook and Twitter.
9. Blip. SMS style voice messaging, which is good because messages do not play immediately like in some of the other applications. Quite clear interface. Offline users will receive their message as an e-mail attachment. It has to be checked still if this style of interface is great for dialog-style communication, or rather just for occasional messages.
10. GO SMS Pro. A SMS application, but also integrating PTT style voice messaging and text chat using data rates.
11. pushFone.
12. Voicely. Includes voice and text messaging.
13. blip.me.
14. FreePP. Multimedia chat application including a PTT button, emoticons, photo sharing etc.. Might be a bloated app as per user reports, but that has to be checked.
15. Walkie Talkie PTT Lite. Includes a message history for replay, and also allows to send voice messages to a group [source]. There are instructions how the data transfer of this app can be encrypted by using IMAP/S. This version has ads, the pro version has not.

Could not be tested so far:

1. digisocial. The start of a very nice PTT application, but still in beta as of 2012-08-10. Because of its beta state, it had some bugs that made playing messages impossible on the phone used for testing. But When it finally starts to work and can be tested for real, it might easily get a recommendation here. It includes, among other things: sending text, smilies, images from the gallery, camera images, location information and of course voice messages; playback selectable via speaker or earset.
2. Voxer. (Version from 2012-07-13, 2.3 MiB) In widespread use and often recommended. One of the most compact apps in this list. Needs at least Android 2.2, so not usable for some older phones like the HTC Magic and for that reason not tested here so far. Includes one-on-one and group messaging, as text, PTT voice message, photo message and location sharing.
3. TiKL Touch Talk Walkie Talkie. Seems to be the most widespread PTT app on Android. It normally registers users by their mobile number so that one does not have to create an account. That however failed as my SIM did not contain that number, leaving me only with the fallback option of logging in via Facebook. And that's no option. What actually is this Facebook?