I'd like to restate what some others have been saying, along with a couple additions:
1. It's a very cool idea, but very hard to do (as you have found out). So if it's taking too much time, cut it as a feature.
2. Leave logging in. Preferably, in an XML format so that everything is easily parsable.
3. Log EVERYTHING. The more the better. Log the starting maps (stars, locations in some coordinate system, planets, etc...), log every ship movement, every fleet creation/change, every battle (maybe not which ship shot which, but maybe that would be nice too), what buildings are being built/finsihed, what ships are created, ship destinations, damage of ships and repairs made in orbit and normal. At end of every turn, log all the galaxy settings (each race's rating for economy, military, production, research, etc...) Basically, log so much that people can write some automated tools to replay the game.
3b. Allow the user to determine what granularity the logging happens (default = no log).
4. Allow for screenshots, and in the log would be an indication that a screenshot was taken, and what the file name of that screen shot is.
While I realize that XML logging would be very "wordy" (aka "big"), it can be simple to create filters to remove portions that you don't care about, or transforms to turn the existing XML into any other format you want.
Basically, this logging wouldn't be for a regular person to just look at and say "Oh yeah, I did this and then this and then this." It would be made in a way that tools can be created for it.
Just my 2 cents.