Correct that Related Pages aren't versioned, however the pages that you relate to can be versioned (just not the relationship itself).
So you can have Page A have Page B as a relationship, and page B can be unpublished, or have it's own workflow, but you can't have Page A have Page B as a relationship for it's current version but have Page C as a relationship for a different version
The only way around it, sadly, is to not use Related Pages for this, and do something along the lines of a long text field with node guids in a pipe separate list...which isn't great because there's no "clean up" in those relationships.