This is something I've noticed in a couple of games. The enemy sovereign appears to visit a goodiehut or possibly a quest hut, and then gains a permanent bonus to their strategic movement. On Ludicrous difficulty, this bonus comes in waves of +5 (maybe not). The issue seems to be more significant the larger the map (more goodie huts?). I've seen a goblin leader with 43 strategic movement.

Here's an unmodded game with Procipinee having 7 strategic "base moves".

http://img404.imageshack.us/img404/2661/elemental1291433572.jpg

edit: a few turns later, up to 9 http://img718.imageshack.us/img718/5729/elemental1291433865.jpg then 10 just after. Now, IF this is from the repeatable technology that increases movement, I think this needs a balance pass. This is only around turn 150 into the game. However, the units from her army does NOT have larger-than-normal movement.