Just occured to me that if you don't mind spending 8 bytes per axis coordinate, you could store locations as both a float and an int, using the int values to store entity locations outside the camera range and then switching over to using the float once things get inside the visible area. That'd give you lots of galaxy space to play with and a lot less overall inaccuracy. Apparent downside is that you'd probably need to do a bunch of workarounds to get it to work smoothly (ie, not using EntityDistance on two objects both using Intspace and that sort of thing).
You'll still want to keep your starship at the origin and move the universe around it, though.
You'll still want to keep your starship at the origin and move the universe around it, though.