Press * at any time for voicemail.

gather.xml

<Response>
    <Gather action="handler.php">
        <Say>Press 1 to do some stuff.</Say>
        <Say>Press 2 to do some more stuff.</Say>
        <Say>Press star to leave a voice message</Say>
    </Gather>
</Response>

handler.php

<?php
$digits = $_REQUEST['Digits'];
?>
<Response>
<?php if ($digits == "*") {
    echo "\t<Say>Leave a message and someone will call you back.</Say>\n\t<Record />";
} else {
    echo "<Say>Other stuff...";
}
?>
</Response>