All perfect praise be to Allah, The Lord of the Worlds. I testify that there is none worthy of worship except Allah, and that Muhammad is His slave and Messenger.
We will summarize our answer to your question as follows:
1- Seeking refuge in a creature in matters that he is able to do is not forbidden, and the scholars have established that this is permissible. Shaykh Ibn Taymiyyah said in ar-Rad ‘ala al-Bakri:
“As for seeking help of a creature in that which he is able to do during his life, then this is permissible, whether this is called seeking refuge, or seeking help, or otherwise.” [End of quote] The Sunnah indicates the permissibility of this. Jaabir, may Allah be pleased with him, reported that a woman from the tribe of Makhzoom committed theft. She was brought to Allah's Messenger and she sought refuge (intercession) from Umm Salama, the wife of the Prophet . Thereupon, the Prophet . said: “I swear by Allah, even if she were Faatima, I would have her hand cut off.” Ibn Hajar said in Fat-h al-Baari: “So she sought refuge in Umm Salamah”, meaning she sought protection [assistance/help] from her.” [End of quote]
2 - Likewise, the Hadeeth which you referred to in your question, which is in Saheeh Muslim. The Hadeeth was narrated by Abu Mas’ood al-Ansari: that he had been beating his slave and the latter started saying: ‘I seek refuge with Allah’, but he continued beating him; then, he said: ‘I seek refuge with Allah's Messenger’, and he spared him. Thereupon Allah's Messenger said: ‘By Allah, Allah has more dominance over you than you have over him (the slave)’. He said: ‘So, I set him free.’” [Muslim]
Abdur-Razzaq narrated it in al-Musannaf from al-Hasan as a Mursal Hadeeth, with the wording: “While a man was beating his slave, the latter said: ‘I seek refuge in Allah’; then he saw the Prophet and said: ‘I seek refuge in the Messenger of Allah...’ etc. The slave sought refuge in the Prophet meaning he sought his protection when he saw him while Abu Mas’ood did not see him. An-Nawawi said when interpreting this Hadeeth: “The scholars said: ‘Perhaps he [Abu Mas’ood] did not hear the slave’s first refuge [i.e. when he said I seek refuge in Allah], due to the intensity of his anger; likewise, he did not hear the call of the Prophet [i.e. when he told him: Allah has more dominance over you than you have over him], or that when he sought refuge in the Prophet Abu Mas’ood noticed the Prophet’s presence.” [End of quote]
3- The same thing was reported by Imam Ahmad in his Musnad from ‘Aa’ishah who said: ‘Safiyyah sent to the Messenger of Allah, food that she had cooked for him while he was with me, so when I saw the female servant [who brought the food] I became so angry that I hit the vessel and threw it on the floor. The Prophet looked at me, and I noticed the anger in his face, so I said: ‘I seek refuge in the Prophet from cursing me today.” Hence, she sought refuge in him from cursing her because of her breaking the vessel [full of food], and it is a matter which the Prophet was capable of.
4- Everything that was mentioned in the previous Ahadeeth was about seeking refuge with a person who was present and capable, so it is totally different from seeking refuge with the jinn who are not seen by man at all. Ibn Abul-‘Izz said in Sharh al-‘Aqeedah at-Taahawiyyah: “It is not permissible to seek refuge in jinn as Allah rebuked the disbelievers about this; Allah Says (what means): {And there were men from mankind who sought refuge in men from the jinn, so they [only] increased them in burden.} [Quran 72:6] They said: ‘When a human being sets down in a valley, he would say: ‘I seek refuge in the great and leader of jinn of this valley from the evil beings in it, so he stays there overnight in security and peace until the morning. {So, they [only] increased them in burden}, means mankind increased the Jinn in burden, by seeking refuge in them; {burden}, means in sin, tyranny, and evil, and the courage and audacity to overcome the humans. So, they said: we have made the jinn and humans as our leaders. Hence, the jinn dignified itself and increased in disbelief when the humans dealt with them in such a way.” [End of quote]
5- Seeking refuge with the jinn or other creatures in that which only Allah can do: this involves polytheism because it can only be done by believing that they have control over the universe, whereas it is Allah Alone Who disposes of the universe and controls it. Therefore, whoever seeks refuge with a creature believing that he has control in the universe, then he has made him as a partner with Allah.
Allah Knows best.