Update: I don't have a query to find all messages with 2 or more labels. However, it sounds like you're trying to make Gmail behave more like IMAP (e.g. folders instead of labels). Instead of using "folders" in Gmail, I think you can continue using them as labels and your IMAP client will just adapt correctly, here's why...
Even though your mail client doesn't support labels, Gmail's IMAP feature compensates for this and allows the folders in your mail client to act as labels.
This means that some messages will appear in both folders, but will still be the same message (e.g. if you delete one, the other one will be deleted as well).
what [...] if I move a message from one folder (in the IMAP client) to another already containing that message?
According to Google's article, How do actions sync in IMAP?, I would guess that it simply removes the original label from the message and leaves the new one on there. Rather than having two messages in the same folder, you should only see one.
Or if I want to delete a message, not just remove a particular label?
According to Google's article, you move it to the trash to delete the message.