I have a bunch of messages that over time I have archived instead of
deleting. I definitely know I do not want them around. What I'm looking
for is a way to easily find these messages so I can delete them. What
would help is to find

"All messages not in inbox and do not have a label"

I've tried starting with just finding all messages not in the inbox and
can't even do that:( I've tried -in:inbox and !in:inbox,  not in:ibox,
but I still get back inbox messages when I ever I have in:inbox
somewhere in the criteria.

Just click on "all mail".  Anything that's been archived will show up
there.

No but the problem is that really shows "ALL" mail... I want to filter
it by stuff that isn't labeled AND isn't in my inbox. (Basically I'm
looking for a way to see all mail that I've tried to archive, which I
know probably isn't easy, so the closest I could come to it is finding
all mail than isn't still in my inbox and doesn't have a label. I'm
basically wanting to truly delete a bunch of stuff that I had one time
archived that I know I don't want).

here is a list of ways that you can search your mail by

at http://mail.google.com/support/bin/answer.py?answer=7190&topic=1578

Yes, I've looked at all of them before I even posted my question.
That's why I figured -in:inbox would work but it doesn't seem to have
any affect.

you can`t filter any mail that you have already gotten the filters will
only work for incoming mail only.

But that's the problem WW, you get back EVERYTHING in All Mail so it'll
take forever to star/checkbox all the messages intermingled between
ones I want. It seems like there isn't a way to perform a search I
want? (ie return messages that are no longer in the inbox? and without
a label?)

I'm not concerned with filtering at the moment, just searching.

Rick,

First of all it looks like in: and label: do exactly the same thing as
"inbox" is just a label too.   You must be doing something wrong
because when I tried -in:inbox or -label:inbox I got ONLY messages NOT
in the inbox.  Are you using the Search box and button at the top of
the page when you are looking at your inbox?   The Search Options page
doesn't give you the opportunity to make these entries.

Now the "no label" part of your question is more difficult.  I'm sure
there is some reserved word, or designation, for "empty".  But, it is
not the ones I'm used to seeing and using like "blank", "NULL", '' (two
single quotes).   So, something like label:'', or label:blank, or
label:NULL, or even label:'NULL' do NOT work.  And, of course
label:(with nothing after ":") returns ALL messages.  The only way I
found to work is to use -label:inbox -label:mylabel -label:mylabel2
etc....   listing ALL my labels.   I know this is a pain if you have a
lot of labels like I do, BUT it DOES work.

Paul