I am having the same issue also, when exporting to pdf. The problem doesn't occur when exported to a jpg. It seems to have started after SP2 was installed. I've attched two screen shots: the original mxd and the exported pdf.
I just started noticing this very same issue for v.10 sp2. I'm sad that everyone else is having to deal with it, but kind of glad that I haven't gone crazy, that this is a known bug. I'll try some of the workarounds. I get it for both v.9.3 and v.10 gdb annotation.
Thanks for the work-around - though goofy, it did the trick! I'd like to add that I've experienced this problem with layers that are shapefiles as well, though other geodatabase feature classes were also drawn into the map with labels turned on. Additionally, I've had both labels AND annotation draw outside the dataframe after exporting. Glad to see its been logged as a bug with severity "High". I hope a patch is released soon!