Is there an efficient way to recover un-synced Photo Stream images?
Directly no.

You can go the indirect route. Get all the photos to a computer, clear the photo stream manually, then enroll the computer into Photo Stream to inject the photos back into the stream in whatever order you prefer.

At that point, you can re-attach the iOS devices to the stream.

You might want to poke at the iOS side (restore or otherwise isolate the issue as it might be a software or network issue there - I've tried to break photo stream with bad network connections - lots of photos taken when offline or switching network from WiFi to 3G and back while taking pictures and it seems pretty robust to me and unbreakable when the software is working properly)