As I've said before on occasion, the HHGTTG canon is … complicated.
In simplest terms, this is just not covered in the books, but the ending of the final fit of the radio series offers some hints as to what might have happened.
In the final episode of the series, the babel fish saves Dent et. al. from destruction at the hands of the Vogons, calling them through the Whole Sort of General Mish-mash to the Restaurant at the End of the Universe, where Fenchurch has been waiting for Arthur at the end of time, and Trillian and Tricia McMillan are merged, essentially undoing the final step in the plan to destroy the Earth and all traces of it.
This doesn't relate to Elvis per se, but it indicates that
the plan to eradicate the Earth and all its children simply failed, neatly resolving the problem of his continued presence at the Domain of the King.
If the books are kept as the only source, then the matter is simply unresolved, although
And Another Thing... introduces new complexities and twists, wherein the plan again simply fails, and his continued presence requires no further explanation.