No idea what Beehive is, sorry, but:
Re: The basic problem is that deleting an email in Aquamail on my phone makes the email disappear from all Zimbra/Beehive mail folders.
Please try this: long press on the account -> options and folders -> IMAP options and turn off "IMAP optimizations".
With these enabled (default), Aqua Mail uses "UID MOVE" (if supported by the server, optional).
With these disabled, Aqua Mail uses a sequence of commands, "UID COPY to dest folder" + "UID STORE +\Deleted" + "UID EXPUNGE".
Maybe it'll help, who knows.
Re: tech support at my company is clueless so far
If they want to see actual commands sent by Aqua Mail, then can do it by enabling the app's debug log:
http://www.aqua-mail.com/?page_id=232K9 has a logging capability too.
And then they can connect to the server using telnet or openssl and repeat the same commands and then try to vary them a bit to see what the trigger is.