3 Columns, 3 Categories, One Archive, and Pagination

OK this is what I ended up with, that works well:

// get paged value.
$paged = get_query_var( 'paged' );
$maxPages = array();
$max = 0;

// Create the queries
$soundPosts = new WP_Query('posts_per_page=1&cat=4&paged=' . $paged);
$viewsPosts = new WP_Query('posts_per_page=1&cat=5&paged=' . $paged);
$wordsPosts = new WP_Query('posts_per_page=1&cat=6&paged=' . $paged);

// get max number of pages for each query
array_push($maxPages,$soundPosts->max_num_pages);
array_push($maxPages,$viewsPosts->max_num_pages);
array_push($maxPages,$wordsPosts->max_num_pages);

// get the max number of pages from all three.
$max = max($maxPages); 

// If we are out of posts, return 404
if ($paged > $max) {
$wp_query->set_404();
status_header('404');
}

// proceed as normal.
get_header(); 

Then for the pagination links, just a bit of logic from the variables created to decide whether to show the links or not.

<?php 
if ($paged > 0 && $paged < $max) { ?>
    <div class="left"><?php previous_posts_link('&#60; Previous') ?></div>
<?php 
}
if ($paged <= $max) { ?>
    <div class="right"><?php next_posts_link('Next &#62;','') ?></div>
<?php } ?>