I just thought of what might be the perfect UI for instant voice messages. Here's how it would go.
Any time when you might press the "Call" button to place a call (such as after entering a number or navigating to a stored number), instead press and hold down the "Call" button. After one second the display says "Recording." Speak your message. When you let go of the "Call" button, recording stops and your instant voice message is sent.
This (a) is super easy, (b) keeps the voice message short, (c) prevents you from leaving the phone in recording mode inadvertently, (d) can be done purely in software on any existing phone design with no extra buttons required, and (e) lets you use all the existing dialing methods on your phone (e.g. dialing the actual number, entering a speed-dial code, redialing a number in your call log, or calling someone in your contact list).
Update: What a remarkable coincidence that less than 24 hours later, Apple announces their new phone with exactly the kind of voice message pickup UI that i was thinking would be perfect for instant voice messages.