I think Romanus is right. There last known velocity when everything shut down would be accurate unless they hit something right?

"If they're going at relativistic speeds, a simple spectroscope could give them a good idea of how fast they're going"

Do you mean by this; measuring and calculating the redshift of known stars if an external view of space is possible?