That's just something that's going to happen with your video, unless you shoot it progressively or something.
Deinterlacing is your only real tool you can use, although some deinterlacers are better than other. Maybe you could look into adaptive deinterlacing or something.
Why are you deinterlacing, anyway? What medium is your final project going to end up on? If it's for TV, leave the interlaced lines because it'll look fine on the TV screen.