Have you tried using your first method, but separating out the UV islands a bit and giving the Normal Bake a margin?