I have found Onyx completely safe to use. After recommending it to many people I have never heard of one problem with it. Most people are astonished as to the depth of its functionality. In fact, one of my favorite Apple-related podcasts, MacGeekGab recommends it on every second or third show to solve some problem or another.
As far as whether rebuilding the mailboxes is different using the Mail.app menu item or Onyx I honestly don't know. One thing that you might want to try is a terminal command that cleans the Mailbox "envelope index." Note that this command is designed for Mail.app on earlier versions of the Mac OS (notice the "V2" in the command - I believe the new Mail.app uses a "V3" mailbox - and so may not work, but it is almost impossible for it to cause any damage. (That said, I always remind people to back up FULLY before attempting anything with terminal commands that they're unsure of or unfamiliar with and that applies here.)
It annoys me that this has to be done in the Terminal. Something like this should be an option in the Mail.app preferences and not force people to use an arcane entry point to the otherwise-elegant Mac OS interface.
I hope this helps. Good luck.