Multiple parameters in a custom post type url rewrite

Probably one of the simpler ways to do this would be to make venue suburb a non-hierarchical custom taxonomy. When you create a venue post, add a term for the suburb and assign it to that post. The register post type rewrite parameter contains a reference to the %venue_suburb% tag, then you can filter post_type_link to substitute that tag for the selected venue suburb term:

add_action( 'init', 'wpa65770_venue_custom_types' );

function wpa65770_venue_custom_types() {

    // extra parameters for tax and post type trimmed to save space
    register_taxonomy( 'venue_suburb','venue',
        array(
            'hierarchical' => false,
            'show_ui' => true,
            'query_var' => true,
            'rewrite' => array( 'slug' => 'venue-suburb' ),
        )
    );

    register_post_type( 'venue',
        array(
            'public' => true,
            'query_var' => true,
            'rewrite' => array( 'slug' => 'venue/%venue_suburb%' ), // rewrite with %venue_suburb%
            'hierarchical' => false,
            'supports' => array('title', 'editor', 'thumbnail')
        )
    );

}

add_filter( 'post_type_link', 'wpa65770_venue_permalink', 10, 3 );

function wpa65770_venue_permalink( $permalink, $post, $leavename ) {
    if ( false !== strpos( $permalink, '%venue_suburb%' )
        && $venue_suburb = get_the_terms( $post->ID, 'venue_suburb' ) ) {
        $permalink = str_replace( '%venue_suburb%', array_pop( $venue_suburb )->slug, $permalink );
    }
    return $permalink;
}

When you create a post, you’ll see the %venue_suburb% tag in the URL until you associate a term to the post. Be sure to visit your permalinks settings page in admin once you add the above code to flush the rewrite rules so this all takes effect.

EDIT- Another version based on your code. You’ll have to modify it to extract suburb from your serialized meta, I just tested with a string val for address:

add_action('init', 'myposttype_rewrite');
function myposttype_rewrite() {
    global $wp_rewrite;
    $queryarg = 'post_type=venue&venue=";
    $wp_rewrite->add_rewrite_tag("%suburb%', '([^/]+)', $queryarg);
    $wp_rewrite->add_permastruct('venue', '/my-venues/%suburb%/%venue%/', false);
}

add_filter('post_type_link', 'venue_permalink', 1, 3);
function venue_permalink($post_link, $post_obj, $leavename) {

    $post = &get_post($post_obj);
    if ( is_wp_error( $post ) )
        return $post;

    $address = get_post_meta( $post_obj->ID, 'address', true );
    $newlink = str_replace( '%suburb%', $address, $post_link );
    return $newlink;
}