First things first, the Shire (as "the Shire") likely didn't exist until four years after the Witch-king fled eastwards, when Bucca of the Marish became the first Thain.
1975 Arvedui drowned in the Bay of Forochel. The palantíri of Annúminas and Amon
Sûl are lost. Eärnur brings a fleet to Lindon. The Witch-king defeated at the
Battle of Fornost, and pursued to the Ettenmoors. He vanishes from the North.
1979 Bucca of the Marish becomes first Thain of the Shire.
Appendix B: Tale of Years
Hobbits (or Periannath) had first moved into the area centuries before, migrating from the East of the Misty Mountains and settling at Bree around the year 1300 of the Third Age (ibid.). Around the same time the Witch-king settles in the North. It is however another 300 years (in 1601) before the Periannath are granted lands beyond the Baranduin. Around 30 years later the Stoors from Dunland join the "Bree-landers" in their new lands.
After the plague of 1636 where the Periannath suffer great losses, nothing is said of them until Bucca is named the first Thain.
So if the Hobbits had lived there lived in the lands beyond the Baranduin for 300 years why were they never attacked. The main reason would be because the Witch-king was not sent to destroy all the lands and the peoples within, but to attack the Dúnedain of Arnor and while the realms (of Arnor, as opposed to the strength of Gondor) were in disunion to topple them.
It was in the beginning of the reign of Malvegil of Arthedain that evil came to Arnor. For at that time the realm of Angmar arose in the North beyond the Ettenmoors. Its lands lay on both sides of the Mountains, and there were gathered many evil men, and Orcs, and other fell creatures. [The lord of that land was known as the Witch-king, but it was not known until later that he was indeed the chief of the Ringwraiths, who came north with the purpose of destroying the Dúnedain in Arnor, seeing hope in their disunion, while Gondor was strong.]
Appendix A, Annals of the Kings and Rulers: ... : The North-kingdom and the Dúnedain
As such the Hobbits are of no interest to the Witch-king or Sauron, who provide no strength to oppose them or ties to Gondor to aid in times of distress (although in the next 1500 years this is proven quite wrong by one young Frodo)
Furthermore, this may also be because in his many thousands of years of living, the Witch-king never developed a sense of humbleness. Something few aside from Gandalf, who had learnt it in Aman1, had learnt and practised.
It is said of Gandalf that among the wise he was “… the only one that goes in for hobbit-lore: an obscure branch of knowledge, but full of surprises. Soft as butter they can be, and yet sometimes as tough as old tree-roots.” (FR). Gandalf was the only outsider to truly take an interest in them and did so as early as the Great Plague, less than 40 years after they'd moved into the lands beyond the Baranduin:
I began to have a warm place in my heart for them in the Long Winter, which none of you can remember. They were very hard put to it then: one of the worst pinches they have been in, dying of cold, and starving in the dreadful dearth that followed. But that was the time to see their courage, and their pity one for another. It was by their pity as much as by their tough uncomplaining courage that they survived. I wanted them still to survive.
Unfinished Tales, Part 3, Chapter III: The Quest of Erebor, Appendix
In contrast, the arrogance of the Witch-king, who was sent to destroy the survivors of Númenor not the entirety of Arnor, had little interest in learning of Hobbits and especially not enough to discover their existence.
The Witch-king's arrogance was, however, not the only factor at play. The Hobbits had gone unnoticed by most everyone and at times of war "... most of them fled into hiding." (Appendix A) (Although they had participated in the wars against Angmar: "To the help of the king they sent some archers who never returned; and others went also to the battle in which Angmar was overthrown." (ibid.))
It must be remembered that while there was no magic about them, they had (extra)ordinary abilities which... "helps them to disappear quietly and quickly when large stupid folk like you and me come blundering along, making a noise like elephants which they can hear a mile off.". This trait almost certainly aiding them in remaining hidden and out of sight from any prying eyes
The lack of knowledge was not limited, however, to the Witch-king. As is seen in the Lord of the Rings, captains of Gondor, including Faramir, are unaware of the existence of Hobbits. As well as the people of Rohan who live closer to Eriador and nigh on the borders of the land of the Stoors of old.
Finally, it seems even after all the long years, when given the name of "Shire" and "Baggins" by Sméagol Sauron and his Nazgûl searched in entirely the wrong area:
They were told also by Khamûl that no dwelling of Halflings could be discovered in the Vales of Anduin, and that the villages of the Stoors by the Gladden had long been deserted. But the Lord of Morgul, seeing no better counsel, determined still to seek northward, hoping maybe to come upon Gollum as well as to discover the Shire.
Unfinished Tales, Part 3, Chapter IV: The Hunt for the Ring
Gandalf, who lived in Lorien (in Aman) travelled often to the house of Nienna and it was there that he "learned pity and patience." and that in later days he was "friend of all the Children of Ilúvatar, and took pity on their sorrows; and those who listened to him awoke from despair and put away the imaginations of darkness."
Credit to Thomas Snerdley for finding some of the quotes