I regularly play as Lannister and my girlfriend plays as Stark. We use the base sets at the moment but are getting the expansions in the next few days.

I want to know if there are any strategies for killing Ned and him not going back to their deck. I find him pretty annoying although can still win games against Stark.

Buy the Lord of Winter expansion, use the Nightmares event. It will blank his Stalwart so he dies and stays dead. The event is great for almost any purpose.

While there are several strategies (for instance, using "Nightmares" from the Lords of Winter expansion to blank his text), or the "Fortified Position" plot, then killing him. There are ways to discard the top card of an opponent's deck (typically out of Greyjoy, known as "Mill" effects) once you know Ned is there. You can use tricks ("White Raven", or the plot "Blockade" or "Fear of Winter") to force him to keep Ned in-hand after drawing it, then win an intrigue challenge to sit ned in the discard pile permanently.

But all that said, Ned "recycling" isn't all that worriesome. You now know one of the two cards he's going to draw - and you know exactly what it does, how much gold it costs. He's only drawing one "new" weapon to use against you every draw phase, while you're drawing two. Sure, you might prefer he draw something else, but you can use that knowledge to your advantage.