I was actually able to recreate the problem - I tested a couple of versions of the same Illustrator graph (one saved as a CS4 EPS, one saved as CS3 EPS), placing each into a picture box in InDesign, altering them slightly, updating them... What i found was if the InDesign preference 'Preserve Image Dimensions When Relinking' was turned on, updated links would scale randomly as mentioned above. Turn the preference off, and everything updated normally.
'Preserve Image Dimensions When Relinking' is the default setting in ID, if I'm not mistaken, so if it is a BUG, obviously Adobe needs to fit it in the near future.
Why would you say this is a bug? If you ask ID to preserve dimensions in the preferences then images must be scaled.
@ Viznavi, edit the prefernces to change the behavior on relink to preserve scaling.