Auto-complete or auto-suggest from list of post titles

Yes this is possible.

You can use jQuery Auto Suggest which is included with WordPress http://codex.wordpress.org/Function_Reference/wp_enqueue_script

With this you can write a form that does a Ajax lookup to the the Ajax URL handler.
Which you can add_action onto. http://codex.wordpress.org/AJAX_in_Plugins

So you can ajax lookup and then on the action side you can just perform a get_posts to match titles, or a raw sql Query. And return what is needed.

That should help, if I get time shortly I might write a full code solution.
But the bulk of it is a whole plugin to help power the lookup.

Edit: Here we go, something like this should do it, haven’t tested it just wrote it off the top of my head.
Update: Escape the Entered text, narrow by custom post type and to published posts only

2012-11-21 Edit: updated typo in code sample.

add_action('wp_enqueue_scripts', 'se_wp_enqueue_scripts');
function se_wp_enqueue_scripts() {
    wp_enqueue_script('suggest');
}

add_action('wp_head', 'se_wp_head');
function se_wp_head() {
?>
<script type="text/javascript">
    var se_ajax_url="<?php echo admin_url("admin-ajax.php'); ?>';

    jQuery(document).ready(function() {
        jQuery('#se_search_element_id').suggest(se_ajax_url + '?action=se_lookup');
    });
</script>
<?php
}

add_action('wp_ajax_se_lookup', 'se_lookup');
add_action('wp_ajax_nopriv_se_lookup', 'se_lookup');

function se_lookup() {
    global $wpdb;

    $search = like_escape($_REQUEST['q']);

    $query = 'SELECT ID,post_title FROM ' . $wpdb->posts . '
        WHERE post_title LIKE \'' . $search . '%\'
        AND post_type = \'post_type_name\'
        AND post_status = \'publish\'
        ORDER BY post_title ASC';
    foreach ($wpdb->get_results($query) as $row) {
        $post_title = $row->post_title;
        $id = $row->ID;

        $meta = get_post_meta($id, 'YOUR_METANAME', TRUE);

        echo $post_title . ' (' . $meta . ')' . "\n";
    }
    die();
}