What would make all content of a certain type return a 404 on the node page?
The author of the nodes in question (just happened to be the same author for all of the nodes in this content type) was missing from the user table. To be clear, the user was not properly deleted - the row was simply removed from the database.

I'm guessing that this caused the db_fetch_object() function to fail within node_load() when it tried to JOIN the user table on the nonexistant uid:

$node = db_fetch_object(db_query('SELECT ' . $fields . ' FROM {node} n INNER JOIN {users} u ON u.uid = n.uid INNER JOIN {node_revisions} r ON r.vid = n.vid WHERE ' . $cond, $arguments));


But it failed completely silently - I that's guess because this scenario would never happen if the user had been deleted properly (Drupal 6 automatically sets the Author of all content created by a deleted user to Anonymous (uid == 0).

Lot's of red herrings while troubleshooting, but maybe this will help someone in the future that doesn't realize they're using a half-sanitized database.