Uffe, there is a way to use labels, according to some people:

http://violentnecessity.net/post/gmail-labels-in-mailbox.app

I haven’t tried it, so I can’t vouch for it. After I get the app, I’ll probably report back with my impressions on this way of using labels.

I believe the developers have stated that they think search is the way to go, versus using labels, but I agree that one size doesn’t fit all. About 95% of what I label could probably be found just as easily with search, but that 5% could be a deal killer if labels don’t work with the app (for example, I receive many pitches for content for this site, and I like to keep them all filed away under one label for easy access. Every pitch is different, so there’s no way I’d find them all with search).