Nick from the awesome MTJ recently posted an article about this plugin: QuickRebuild. It is totally and utterly great, and I'm not saying this because this plugin saved me several hours of tedious clicking today (well, actually I am).
Basically the plugin adds an extra 'rebuild' icon to your menu bar that gives you the option to rebuild all your blogs in one go (or just a subselection of them). You can download it here.
Oh, and the documentation is lying: it does work with MT5, which makes it even better.