Message-ID is something already stored in your email database, because it's necessary for a lot of stuff (in particular, threading conversations correctly). I'd be shocked if any email store didn't support querying by message-ID. Querying by body is a lot harder, since you need full-text support in the body. It's not the difficulty of implementing mid that's blocking support in clients.