Ok, firstly let me just break it down a little, so you understand the purpose of these functions.

• wp_enqueue_script()

  Description:
  A safe way of adding javascripts to a WordPress generated page. Basically, include the script if it hasn’t already been included, and load the one that WordPress ships.

• wp_localize_script()

  Description:
  Localizes a script, but only if script has already been added. Can also be used to include arbitrary Javascript data in a page.

When you localize a script, all you’re doing is setting up an action that prints out Javascript vars into the page, but these vars are tied to the script you register them to, it’s the first parameter you pass to wp_localize_script and is otherwise known as the script handle.

wp_enqueue_script is for queuing a javascript file, and wp_localize_script is designed to accompany scripts loaded via the enqueue system. You cannot localize nothing, so if you’re not enqueuing, wp_localize_script is of no use to you here.

Typically you’d likely use the two like this..

$myvars = array( 
    'ajaxurl' => admin_url( 'admin-ajax.php' ),
    'somevar1' => $somevar_from_somewhere,
    'somevar2' => $somevar_from_elsewhere
);
wp_enqueue_script( 'my-ajax-request', plugins_url( '/path/to/somefile.js', __FILE__ ) );
wp_localize_script( 'my-ajax-request', 'MyAjax', $myvars );

Which then produces the following output in your page..

<script type="text/javascript" src="https://wordpress.stackexchange.com/questions/13277/path/to/somefile.js"></script>

<script type="text/javascript">
/* <![CDATA[ */
var MyAjax = {
    ajaxurl: "http://example.com/wordpress/wp-admin/admin-ajax.php",
    somevar1: "somevalue",
    somevar2: "someothervalue"
};
/* ]]> */
</script>

Which you can then reference in your script, eg.

jQuery(document).ready( function($) {

    alert( MyAjax.somevar1 ); // Produces somevalue
    alert( MyAjax.somevar2 ); // Produces someothervalue

});

Throwing this all together, your code could go a little something like this..

// Setup the ajax callback for the "searchmap" action 
add_action( 'wp_ajax_searchmap', 'my_searchmap_function' );
add_action( 'wp_ajax_nopriv_searchmap', 'my_searchmap_function' );

// The callback function for the "searchmap" action
function my_searchmap_function() {
    $myposts = get_posts('numberposts=-1&offset=$first');
?>
<div> 
    <h3>Pages</h3>
    <ul>
        <?php wp_list_pages('title_li=&depth=0&exclude="); ?>
    </ul>

    <h3>Posts</h3>
    <ul>
        <?php foreach( $myposts as $post ) : setup_postdata( $post ); ?>

        <li><a href="https://wordpress.stackexchange.com/questions/13277/<?php the_permalink(); ?>"><?php the_title(); ?></a></li>

        <?php endforeach; ?>
        <?php wp_reset_postdata(); ?>
    </ul>

    <h3>Categories</h3>
    <ul>
    <?php wp_list_categories("title_li=&orderby=name'); ?>
    </ul>
</div>  
<?php 
    die;
}

The JS .. (assuming it was enqueued and localized)

jQuery(document).ready(function($) {
    $('a.myajax').click(function(){
        var data = {
            action: 'searchmap' // <--- this is the correct action name
        };
        $.post( MyAjax.ajaxurl, data, function(response) {
            $('#myresult').html(response);
        });
        return false;
    });
});

And then the actual HTML needed in the page to trigger the action..

<a class="myajax" href="#">Click me to fetch ajax content</a>
<div id="myresult"></div>

---

Actual Answer

With regard to needing to do your own thing, and get vars printed out for your script, i’d suggest doing something like this…

add_action( 'wp_head', 'my_js_vars', 1000 );

function my_js_vars() {

    // If it's not a specific page, stop here
    if( !is_page( 'my-page-with-ajax' ) )
        return;
    ?>
    <script type="text/javascript">
    /* <![CDATA[ */
    var MyAjax = {
        ajaxurl: '<?php admin_url('admin-ajax.php'); ?>',
            somevar: 'somevalue',
            someothervar: 'someothervalue'
    };
    /* ]]> */
    </script>
    <?php
    /*
       NOTE: 
       Make sure not to leave a comma after the last item 
       in the JS array, else IE(Internet Explorer) will choke on the JS.
    */
}

I left code that i previously posted for the sake of others reading.