This is something that has bugged me. If you have labels with spaces in the name, the obvious search (such as label:my label or label:"my label") fails to return any messages.

You have to replace the spaces in your label name with dashes/hyphens. So label:my-label will return messages labeled "My Label".