Deinterlacing

Evening all. I'm very new to video editing and hope someone can help me, as I seem to be going round and round in circles. I'm currently trying to convert old home videos to digital format. The captured footage is in MPEG format in 'upper first' field order, and has the horizontal lines (I assume this is interlacing) when the footage is fast moving. I've made some edits (cutting scenes etc) in Premiere Pro, and I'm now trying to export the edited file in H264. Each exported file (trying 'upper first' and 'progressive' field order) still has the horizontal lines, and I can't seem to get rid of these. I've followed the instructions I've found online to go to Field Options>Always Deinterlace but this makes no difference. The only thing that makes the horizontal lines less noticeable is going to Field Options>Flicker Removal, but it doesn't eliminate them entirely. I've also tried creating a new sequence in progressive and adding the footage, but this doesn't make any difference either. Could someone possibly tell me where I'm going wrong? I hope I've provided enough information, but happy to share anything that's needed.