For instance, you might say, "She threw everything at me but the kitchen sink." Here you are emphasizing the way she was acting, not the particular items thrown.
If you were to write, "She threw everything at me but not the kitchen sink," you would be making a straightforward statement about the items being thrown. It would no longer be an expression that is making a point.
Now, in your example first "wallet" example, we would assume that you are emphasizing the thoroughness of your search. Or you might be emphasizing the fact that your wallet wasn't there to see. I'm not sure.
In your second example, however, you are making a straightforward statement that you were looking for something but didn't come across the wallet.
Can you see the difference? It is somewhat subtle. I'm sure that others can explain this better.
Interested in Language