We have a similar setup. Broadly speaking our build steps are 1) Build; 2) Test; 3) Build Docker Image; and 4) Deploy Docker Image.
First, I think it’s a good “best practice” to keep at least some docker images around, particularly for production. If production goes down (say, from a bad merge that wasn’t caught in testing, for example), I can think of nothing I want to be doing less than waiting for a build to complete in that situation. Personally, we keep the most recent hot-fix of every major release and all production deployments for the last month. This may avoid your issue straightaway.
Second, if keeping images around is not possible to do, (and I’m in speculation territory here because we never need to do this because of the above) how does gitlab respond in a redeploy if there is a dependency on a previous build step? I would assume that it would be forced to re-execute the deploy and all previous dependent steps if it/they is/are not available in its cache. If that is the case, as long as you have your deploy step dependent on the relevant build steps, I would expect that it would rebuild. The other way I could see it working is that it might just not let you roll back to that version at all.
Do you have dependencies setup between the CI build stages?