List all nodes under a vocabulary/category [NOT a term]

I'm a newbie here so this might be stupid but have you tried just cutting some php into a block via the cck? I found it to be the fastest and most brutal way to get that kind of thing done. I have an example on my first Drupal page that I believe could be modified slightly to accommodate what your seeking functionality wise.

http://piratemesa.net/node/4

If not, sorry I'm new, this might even be my first post..

I've never tried this, but what about making a new page, flipping on PHP, and doing something like:

<?php
// ID of vocabulary. You'll have to hard code this.
$vid = 1;

// Retrieve all terms for the vocabulary.
$terms = array_map('_taxonomy_get_tid_from_term', taxonomy_get_tree($vid, 0, -1, 0));

// Render all nodes in a pager.
taxonomy_render_nodes(taxonomy_select_nodes($terms, 'or', 'all'));
?>

If that doesn't work, check out the taxonomy functions at http://api.drupal.org/api/5/file/modules/taxonomy/taxonomy.module and see if there isn't something else.

You can always make your own custom module as well, so when a user visits /vocabulary/1 or some such it'll spit out the nodes for that vocab.