Yeah, it's only natural that you'll lose some formatting: not all programs will interpret the file data the same way. My best advice is, keep it simple, otherwise you're more likely to encounter issues.
If it's not a complex Keynote, sometimes the easiest solution is to just export as a PDF. Of course, if you have animations and actions in your slideshow, they won't show up.
That said, I've not tried opening a Keynote (created with '08 and '09) in the latest versions of MS Office, Windows or Mac OS X... Perhaps it's better then older versions.