Thank you for this explanation. 
So, I’m almost at my 55 hours of rebaking my posts containing [img] with a 5-second delay between each iteration of my 40000 posts from my rails script.
From what I see, it works well better than before. Most valid images (I exclude Imageshack and its erratic behavior) seem to be uploaded to my forum flawlessly at first glance at least, but I’ll have a deeper look to be 100% sure. What is 100% sure is that the results are way, way better and consistent.
So I suspect the issue I encountered (and maybe the issue from @Amethi) which was randomness in the remote image downloading with invalidate_broken_images was related to a kind of rate limit from various image hosting providers…? 
The weird thing is that I didn’t notice any issue with my other imported forums… 
That said, if the results are satisfactory enough and the delay really improves the remote image downloading, I’ll do the same method on my production forum, but I’ll increase the time between each rebaked post from 5 sec to 10 or 15 seconds (or even maybe more, we’re not in a hurry, these are all fairly old posts, and the VPS has way lower specs than my own computer).
I do not want to be conclusive too fast, but the solution to my initial problem could be to apply both the solution proposed by Richard AND add a delay between each post rebake.