Ents in the Shire...

[inglorion]

'... Aye, aye, there was all one wood once upon a time from here to the Mountains of Lune, and this was just it's East End.
Those were the broad days! Time was when I could walk and sing all day and hear no more than the echo of my own voice in the hollow hills. The woods were like the woods of Lothlórien, only thicker, stronger, younger. And the smell of the air! I used to spend a week just breathing.'

This is also a quote from Treebeard. He speaks of the days when Elves taught them to speak, before the 'Great Darkness' came. The Old Forest and Fangorn were once connected as one big Wood over the whole of length of Arnor. That explains that once the Ents were walking through all those parts and why there are Huorns in the Old Forest.

Later Treebeard mentions the loss of the Entwives, in the years of Sauron and the Men of the Sea, this probably being the Elendil and his people. The Entwives were the opposite of Ents, who like the wild broad forests, and loved organized gardens, so they made there own. Those were near the Anduin, and are in time of LotR called the Brown Lands. Treebeard says:

'We crossed the Anduin and came to their land; but we found it a desert: it was all burned and uprooted,for was had passed over it. But the Entwives were not there.'

What happened here is unknown, yes, battle was fought, but what happened to the Entwives is unknown. I don't think they were perished in this War, because when the Ents search for them many say they have seen them, yet ever these people pointed in other directions, and so the Ents do never find them.
My conclusion to all this is that the Entwives have been searching themselves as did the Ents, only the Entwives searched for a Land. A land for them to create their gardens anew. This would explain that many people had seen them in many different directions, for just as the Ents the Entwives would search long and far.
After searching for a long time, I guess they settled just North of the Shire, for, as Treebeard says in LotR, that was a land which was to their liking.

He made them describe the Shire and it's country over and over again. He said an odd thing at this point. 'You never see any, hm, any Ents round there, do you?' he asked. 'Well, not Ents, Entwives I should really say.'

The 'He' is of course Treebeard.
The fact that Treebeard makes them describe the Shire AND it's country seems to me as another point on which we might base the idea of the Entwives in the lands north of the Shire.
A point of consideration however is the '7-yard-stride' that Sam talks about. LotR says that Treebeard was 15 feet tall, which is ±4,60 meters. A seven-yard-stride (this being a length of ±6,3 m) seems highly unlikely. Treebeard made, according to LotR, long deliberate strides, yet to assume that a creature made strides larger than his own length seems impossible.
The answer to this seems absurdly simple. The tale of Sam's cousin Hal seeing the Walking Tree would have been told many times and especially in bars and such places. And the ability of Humans, Hobbits etc. to exagerate about length, size or other features of importance, is great. Because, when you see a Walking Tree the thing that matters is that it is walking, it is a possibility that especially the speed of it or the length of it's strides would be exagerated. The 'seven-yard-stride' is an exageration!

To answer the post of Eruantalon:

Sauron indeed scorched the Land in the Second Age! He had all the lands in Darkness and Arnor was fallen apart. Yet at that time the Entwives didn't live in Arthedain, but they had their gardens near Anduin (Brown Lands). Sauron and the War against him scorched those lands as well and their gardens were destroyed and they were lost. But if they were imprisoned or slain, how can people have reported seeing them when the Ents searched for them?
I think they left their lands, alive and free, but grieving for the loss of their gardens, and searched therefore a land that would satisfy them again.

Well... this is how I think of the topic and I hope to have been of help!

greetings,
lathspell