Different bastards, different context
There are multiple bastards in the story, and the two scenes you highlight focus on completely different bastards.
He's found one bastard already.
This is in reference to Robert's bastards, of which Gendry is one but Robert had many others (who were later all killed except Gendry, I believe?). I think he was talking ...
This is at least what happens in the books, so it passes for in-universe canon. I don't know how much can be inferred from the show and if it's consistent, but here goes:
Ned inquired and found out Jon Arryn has asked for 'the book' shortly before death. Such an inquiry of an otherwise uninteresting book piqued his curiosity and he borrowed the book.
Very likely not. Robb sent his men after Jamie with the fastest horses and his order was to bring Jamie back after Catelyn freed him, and this objective didn't change. Roose Bolton releasing Jamie was already a beginning of his tretchery and his conspiracy with Lannisters. Had Robb known this, he certainly wouldn't be celebrating Red wedding with him.
In Season 7 Episode 7, in the demonstration of wight to Cersei, they split the wight in three parts, all of them moving. So, there you have a headless wight.
Not sure if they are marching in the army, but as you can see, it is possible, until they are destroyed with fire, dragon glass or valyrian steel.