Sorry, "bounding box" is terminology from another program. What happens to your arrow when you change the width/height under Size? I see that the "preserve aspect ratio" box is greyed out, so you may be out of luck.
Could you create a copy of the north arrow that simply has negative space on the sides to make it a perfect square? Of course, this still won't help for diagonals, as the main square would shrink to fit within the original size. If that's what's happening here, which we're still not certain of.
Can you give a few screenshots of what the rotated arrows look like in the output?
I may have a remote machine that still has ArcMap on it, and I'll see if I can replicate this.
- Josh Carlson
Kendall County GIS