Well I managed to remove the images from the query editing /tidypics/resources/tidypics/lists/siteimagesall.php eby doing this:

// grab the html to display the most recent images
$result = elgg_list_entities(array(
    'type' => 'object',
    'subtype' => 'image',
    'owner_guid' => NULL,
    'wheres'=>'e.guid NOT IN(SELECT entity_guid FROM elgg_metadata WHERE value_id IN(406))',
    'limit' => $limit,
    'offset' => $offset,
    'full_view' => false,
    'list_type' => 'gallery',
    'gallery_class' => 'tidypics-gallery'
));

Where "406" is the ID of the tag I want picture to not have. Hope someone finds this useful =)

Now I only need to figure out how to add the new tab with the query only showing these tags.

I can't provide you with the ready-to-use code for that (no time at the moment to full code that all) but only some hints that might be useful.

If you haven't seen it yet you might want to check out http://reference.elgg.org/engine_2lib_2metadata_8php.html#aec4b6f0b9565e3554acb9b39ef34a2ac for an example of a where clause to exclude certain entries from a query (not containing a certain metadata). It's similar to what you have come up with but maybe it works even better.

Regarding the additional tab you would have to add the page/view code to be used for this tab, add an entry to Tidypics' pagehandler for this new page and you will have to override the default filter (filter menu is the tabs selection) to add your additional tab. As an example for adding a tab you can take a look into the code of my izap_videos plugin that adds a "Favorite" tab in addition to the default tabs. For the other modifications I can only suggest to look into the code of the Tidypics plugin to understand what is necessary for the creation of the additional tab.

For fetching the images with a specific tab you might need to add some custom join/where clauses. Maybe it helps to look into the code of the elgg_get_tabs() function in engine/lib/tags.php. Using elgg_get_tabs might also work to get an array of image entries that have the desired tag. Though you would have to deal with creating the html output on your own when using elgg_get_tags() whereas Elgg already deals with creating the ready-to-use output when using some elgg_list_*() function. I don't know if you can use elgg_list_entities_from_metadata() without some custom join/where clauses as the tags are not saved as separate metadata entries but instead all tags belonging to an entity are saved as a single metadata (comma separated string with the tag values).