Your third method should be the way to do it. From the information you gave I can't see why that wouldn't work. Couple of things to try: - With your method 3 (animation baked to joints) you're using "Export Selecion" then ensure "Input Connections" export option is checked. - Try instead of deleting your rig just select…
If it's only an issue when you have modelling history on the mesh have you tried "Delete Non-Deformer History"? If it is just a history issue and that doesn't fix it then I'd save the skin weights out, clean up the mesh and then re-bind and import the weights. Also, if you just need to export to an older FBX format then…