Do NOT - repeat NOT - use Exists in this case. Exists only is whether FirstPage or OddEven is being displayed. It has nothing whatsoever to do with whether it exists, or not.
The only part that I am still struggling with is how to detect linked headers. I might give up if I see it's not worth it, but still, I'd like to know how to do it properly.
You were correct in the first place, Link is Boolean, therefore use it as Boolean. And stop using Select!
Dim oHF As HeaderFooter 
Dim oSection As Section 
Dim LinkToPreviousFlag As Integer 
For Each oSection In Application.ActiveDocument.Sections 
    For Each oHF In oSection.Headers 
If oHF.LinkToPrevious = False Then
'it is NOT linked so
' do whatever it is you are doing
End If