There are modules named Mail::IMAPClient, Mail::IMAPSearch, and Mail::IMAPTalk; that seems good enough for me...

And Mail::IMAPBodyStructure looks like an overloading a level of hierarchy too much, does it not?

Sounds to me like that's a vote for Mail::IMAP::BodyStructure...