Text placement is very scale specific. There are many cases where drawing text at the same screen/page size for different map scales will result in text collisions. If you happen to be in the rare case where you can re-size without collisions, use Symbol Substitutions as @Jakub notes. You'll need to calculate a text size to mimic the size seen at the other scales etc.
For cases where you need to generate annotation at different scales, I'd recommend using the Tiled Labels to Annotation tool. This works with data driven pages workflows etc. and can generate different scales.
[UPDATE]
To do the size calculation, it's a matter of remembering that scales are fractions:
original size / anno reference scale = x / new scale
so for a scale where I have twelve point font at a reference scale of 1:90,000,000 and I want that text to draw at 1:400,000,000, do this:
12 / 90,000,000 = x / 400,000,000
which means x ~ 35.56
Setup symbol substitation with a size of 35.56 pts and you'll be ok.
Best Answer
I've experienced issues similar to this while using ArcMap 10.x. When I've changed the size of the map document after I developed the map with symbols and labels. Let me explain further.
For example, my supervisor needs a map to be created on 8 1/2 x 11 paper, I work on the layers, add labels (converted to annotation) and the map is about ready to go.
Then he updates me that it need to be on 11 x 17, so instead of starting from scratch I decide to go to my print settings and adjust the map to 8 1/2 x 11 to 11 x 17 then going to layout view and adjusting the borders on the map canvass to fit the new size that I have chosen.
Everything appears normal until I need to update the labels and all the units appear off. The labels now appear in different sizes even though I'm adjust the font size to equal the same. That one issue that could be causing your situation, you might have adjusted your map layout and that doesn't bode well for the resizing of the font/label/symbology on your map.
This post in GIS SE gives further insight on things to consider in general for your labels.