Dealing with the case that a package version was deleted from the archive

Base on what is appropriate; both the deleted version and the currently present version may be fine, depending on why the deletion was performed.
Rich history import won’t be affected; it just expects your changelog parent to match your rich history base, and that’ll generally be true anyway.
You can’t upload the same version that was deleted, so you may need to “jump” past that version. Exception: in a stable release, ubuntu1 -> ubuntu2 (deleted) -> ubuntu1.1 works.