[Update: Better version over here, that stores the searches serverside so this works from multiple machines]
God bless Greasemonkey. Now I can have stored searches in GMail implemented as a Greasemonkey user script. Justerens comment was on the nose "Isn't that what filters and labels are for?". It is - but filters only applies to new email - and spamfiltering overrides filters. I have consistent problems with specific kinds of ham, that I actually have rules to pick up, that ends up filtered as spam.