For your second example, I think you're initiating your Loop incorrectly. You're declaring $query, which hasn't been globalized?

// Search is working, querying is not
global $query_string; // required
$posts = query_posts($query_string.'&posts_per_page=3&cat=$catid');

while ( $query->have_posts() ) : $query->the_post();

Try omitting $query from your Loop initiation?

// Search is working, querying is not
global $query_string; // required
$posts = query_posts($query_string.'&posts_per_page=3&cat=$catid');

while ( have_posts() ) : the_post();

...and see if that makes a difference?

For the first example, what does "the search Widget breaks" mean?

For your second example, I think you're initiating your Loop incorrectly. You're declaring $query, which hasn't been globalized?

// Search is working, querying is not
global $query_string; // required
$posts = query_posts($query_string.'&posts_per_page=3&cat=$catid');

while ( $query->have_posts() ) : $query->the_post();

Try omitting $query from your Loop initiation?

// Search is working, querying is not
global $query_string; // required
$posts = query_posts($query_string.'&posts_per_page=3&cat=$catid');

while ( have_posts() ) : the_post();

...and see if that makes a difference?

For the first example, what does "the search Widget breaks" mean?

EDIT

Wow, I completely overlooked this: you're passing your variable as a string:

$posts = query_posts($query_string.'&posts_per_page=3&cat=$catid');

Try this instead:

$posts = query_posts( $query_string . '&posts_per_page=3&cat=' . $catid );

...so that your $catid gets parsed properly.