List of nodes that have no taxonomy terms I'm maintaining a D6 project, where the customer wants to see a list of nodes where no taxonomy terms were added.

I want to solve this with views. I already tried some Filter settings for that, but nothing worked so far. 

I would know the solution in D7 with Views 3 but in this case I can't get rid of this problem.
Try this:
1. create a node view
2. in 'Fields', add 'Node: nid'
3. in 'Relationships', add 'Taxonomy: Node'
4. in 'Filters', add 'Taxonomy: Vocabulary', in next step, choose 'Is empty (NULL)' as the operator.
5. test some of the nids given in the preview to see if they are the ones you are looking for, you might need to tweak a little the usage of relationship.
Step #3 is here to give you extra operators to choose from. 



update

Okay the above assumes the content type only has one term field, so nevermind...
Now that I understand the issue better, I think you will probably need views_or module. Also we don't need 'relationship' anymore. 

On my test Views, I use filter 'taxonomy:term(term id)' for each vocabulary, chain them together via Views_or. Set them to dropdown with hierarchy. Then highlight all terms in the vocab and check 'is none of' for the operator on the left. It's a very ugly query but that's the only way I got it to work...You'd better cache it for a better performance. I attached some screenshots hope to clarify the config part.