> Also, If I had rewritten it as
> Он залетел 5000 миль.

It's wrong. "За-летел" implies crossing some border. For example "залетел на территорию", "залетел в ангар", "залетел так далеко как никогда не залетал". It's perfect verb. Also there is slang meaning 'она залетела' - 'she has got unwanted pregnancy' which is clearly derived from idea of 'crossing border'.

> Он пролетел 5000 миль.

It's correct, but 'пролетел' tends to be used in context of mentioned event or time period. For example "он пролетел 5000 миль в этот день". It's strange to see it without such context. In contrast, 'налетал' has implied context 'for all life' (however it can be changed easily).