Is a smoke simulation with more than 512 divisions possible?
Unfortunately, no. Also I believe that it always alocates the same divisions along each axis, so generally you might want to keep it smaller than 512. You could take a look at using the smoke high resolution to get more details. If you want a render at that distance you could consider using particles instead. Or you could divide it into separate shots.

edit: Yes, do as gandalf3 suggests, but you'll need adaptive domain enabled for that. Otherwise it will move the current simulation data.