Looks like I found the answer to my question.
In Mahabharata -> Shanti parv -> Moksha parv -> chapter 230.
Ugrasen asked the same question to Krishna about Why Narad muni is respected by all, and Krishna replied below (I am intentionally not editing out anything, copying all of the phrases):
Vasudeva said, 'O chief of the Kukkuras, listen to me as I mention in brief those good qualities of Narada with which I am acquainted, O king! Narada is as learned in the scriptures as he is good and pious in his conduct. And yet, on account of his conduct, he never cherishes pride that makes one's blood so hot. It is for this reason that he is worshipped everywhere. Discontent, wrath, levity, and fear, these do not exist in Narada. He is free from procrastination, and possessed of courage. For this he is worshipped everywhere. Narada deserves the respectful worship of all. He never falls back from his words through desire or cupidity. For this he is worshipped everywhere. He is fully conversant with the principles that lead to the knowledge of the soul, disposed to peace, possessed of great energy, and a master of his senses. He is free from guile, and truthful in speech. For this he is worshipped with respect everywhere. He is distinguished by energy, by fame, by intelligence, by knowledge, by humility, by birth, by penances, and by years. For these he is everywhere worshipped with respect. He is of good behaviour. He dresses and houses himself well. He eats pure food. He loves all. He is pure in body and mind. He is sweet-speeched. He is free from envy and malice. For this he is everywhere worshipped with respect. He is certainly always employed in doing good to all people. No sin dwells in him. He never rejoices at other people's misfortunes. For this he is everywhere worshipped with respect. He always seeks to conquer all earthly desires by listening to Vedic recitations and attending to the Puranas. He is a great renouncer and he never disregards any one. 1 For this he is everywhere worshipped with respect. He casts an equal eye on all; and, therefore, he has no one whom he loves and none whom he hates. He always speaks what is agreeable to the hearer. For this he is everywhere worshipped with respect. He is possessed of great learning in the scriptures. His conversation is varied and delightful. His knowledge and wisdom are great. He is free from cupidity. He is free also from deception. He is large-hearted. He has, conquered wrath and cupidity. For this he is everywhere worshipped with respect. He has never quarrelled with any one for any subject connected with profit or pleasure. All faults have been torn away by him. For this he is everywhere worshipped with respect. His devotion (to Brahma) is firm. His soul is blameless. He is well-versed in the Srutis. He is free from cruelty. He is beyond the influence of delusion or faults. For this he is worshipped everywhere with respect. He is unattached to all such things as are objects of attachment (for others). For all that he seems to be attached to all things. 2 He is never long subject to the influence of any doubt. For this he is everywhere worshipped with respect. He has no yearning for objects connected with profit and pleasure. He never glorifies his own self. He is free from malice. He is mild in speech. For this he is everywhere worshipped with respect. He observes the hearts, different from one another, of all men, without blaming any of them. He is well-versed in all matters connected with the origin of things. He never disregards or shows hatred for any kind of science. He lives according to his own standard of morality. He never suffers his time to pass away fruitlessly. His soul is under his control For this he is everywhere worshipped with respect. He has toiled in subjects that deserve the application of toil. He has earned knowledge and wisdom. He is never satiated with yoga. He is always attentive and ready for exertion. He is ever heedful. For this he is everywhere worshipped with respect. He has never to feel shame for any deficiency of his. He is very attentive. He is always engaged by others in accomplishing what is for their good. He never divulges the secrets of others. For this he is everywhere worshipped with respect. He never yields to transports of joy on occasions of making even valuable acquisitions. He is never pained at losses. His understanding is firm and stable. His soul is unattached to all things. For this he is everywhere worshipped with respect. Who, indeed, is there that will not love him who is thus possessed of every merit and accomplishment, who is clever in all things, who is pure in body and mind, who is entirely auspicious, who is well-versed with the course of time and its opportuneness for particular acts, and who is well-acquainted with all agreeable things?'"
Apart from that, the question about How he can travel anywhere is explained by 'ram' in the commnent.