Putting the social anxiety issue aside for a moment. If you want to do things properly, it should be done in writing. Period. You write a letter, send it to everyone of your intentions and the date or dates the fence will be removed. 30 days should give them enough time to decide what to do about it and get quotes from professional fence installers or to simply keep their dogs in the house if needed. This is very reasonable and much more polite than them painting your fence and linking to it without your permission. All of this needs to be done in writing, because some people don’t fully understand what is going to happen if you talk to them. Also, if they verbal agree to something, there can be an honest misunderstanding later. So keep it all in writing. In other words, there is no real reason to talk to any of these people face-to-face. This is the proper and respectful way to do things. Also, if you can afford it, I recommend you get someone else to do the fence removal and cart it away. That way, while it’s being removed you can stay out of it. After all, they got the letter, had 30 days, there is nothing else to talk about.
They do have maps, but the problem is they aren’t updated. A new survey would include the fences and it would show exactly what is and isn’t on the property.
We shared a neighbor’s fence in our old subdivision. She told us ahead of time that she was going to put it up. A year or so later, when we went to fence in our yard, we attached our fence to hers, with her blessing. We were willing to pay for 1/8th of her fence (our half of 1/4th), but she refused.
Fast forward a decade. After her dogs died, we realized that she had no use for the fence, and my husband offered to maintain it because we didn’t want her to tear it down because we still had a dog. She said that she was happy to maintain it. Well, she didn’t do such a great job at maintaining it, but she was going through a real rough patch so we certainly didn’t fuss about it. But when we went to put our house up for sale, my husband replaced several of our shared rails (it was a split rail with a liner). She actually came over and offered us money for that, which we refused. She was a nice lady.
So my advice is to write a letter or email, if you simply cannot talk to your neighbors and give them an opportunity to maintain the shared fence, on their own dime, or you plan to tear it down in x days. But I warn you, if you do tear it down, be prepared for their dogs to visit your yard! 
It helps if the dogs are people-friendly and you’re dog-friendly.
I lived in a house for a year. An old college-days friend had this vacant house on his hands (it had been his mother’s) and he invited me to house-sit there, rent-free, until he felt the market was right to sell.
Two neighbors had two dogs each, and the fences were in shabby condition. The dogs were always sneaking into my yard. As it happened, they were friendly playful dogs so I always went out to play with them. In fact, when one of those neighbor’s landlords rebuilt the fence on the other side, I let them keep the dogs in my yard for a few days while they did that.
Now, as it happened, the fence on the other side was shabby too, so the dogs got into the yard on the other side. That drew some complaints, but by the time that came up, I wasn’t living there any more.
Have not read the entire thread, but coincidentally today, I just had a fence installed across the rear of my property.
I did not read where you stated you have your “Plat Of Survey”. That document will show whether your fence in on your property and truly yours…
Since your fence is in questionable condition, just tear it down {giving the dog owners ample notice}.
For example, my plat showed that the fence on one side of my house is mine, the fence along the other side of my house is my neighbors. All I had them do today was fence in the rear portion of our lot today.
.
Wow, I didn’t expect so many replies. Thanks, everyone ( I have some reading to do).
I was wondering about this, because the county auditor real property search has a map that shows outlines of my property and neighbors. When I click I my address my yard is show with yellow lines and the neighboring yards have white borders. I can see my fence in the picture. On one side (not the neighbors in the dispute, and the one that has 2 neighbors without fences) the straight part of the fence is clearly inside. I forgot to mention that on the back left (looking from street) corner the property is angled. So the lot isn’t a perfect rectangle. One neighbor’s back yard borders that angle. It looks like the angle of my fence might stick out a little there.
As far as the straight side that borders the neighbor in the dispute. It really looks like the yellow line runs right on top of the fence, and it might be possible the posts are in my hard but the boards aren’t. If that makes sense. It’s right along that line, at least going off a pic on the county site.
FWIW, My house is 21 years old. My family has occupied it for 14 years. I don’t know if the fence was built when the house was or not. It was here 14 years ago. I can tell from the county site that our deck was built a year after the house. No permit required for fence. I would assume someone used a survey to build it or otherwise had access to property lines at the time. Despite it possible being a little off in 1 corner, how else would they know where to build it?
BE CAREFUL—everything you say in this post is probably irrelevant, and you should NOT rely on it.
You have apparently found the county’s website with its land database. This is almost certainly NOT an official record of your property boundaries…The yellow and white lines are probably just graphical indications of the approximate boundaries, overlayed onto an aerial photograph.
You even describe it as a “picture”, not a map.
A picture is NOT a survey.!!!
The yellow and white lines you mention are probably inserted by a process called “digitizing”-and could be inaccurate by as much as 1 or2 feet. A survey is accurate to one-hundredth of a foot (about a half-inch)
And the website is NOT a legally binding document—it is almost certainly intended only to be a visual aid, showing some general information about your lot (i.e–its location, the fact that it’s a residence, not an industrial site, that it is a half-acre in size, not 1 acre, it has a couple of electrical poles nearby , it is served by school district “X” and garbage-collection district “Y” etc.
Do not rely on this “picture” for any kind of acccurate proof that your fence is on your property. For that, you need a survey map.
Sorry - I can’t let this blow by. One one-hundredth of a foot is .12 inches, or roughly 1/8 of an inch. And yes, when surveying land, the size of the markers make those two degrees of accuracy pretty much irrelevant.
Carry on.
And without an honest-to-goodness survey, you can’t be certain of where your property line really is, as others have said.
QFT. I work for County GIS and run such a website. It is not binding at all and not necessarily accurate. The County should have a disclaimer stating that it is not up to survey standards.
actualliberalnotoneofthose - It would not hurt to look through your mortgage papers. You should have what is called an Improvement Location Survey/Certificate (ILC). It’s a ‘map/survey’ of your property required by title companies. These are done to show that your house and outbuildings are indeed on your property and are not encroaching into easements or other properties. I DON’T think it’s going to say anything about fences though. BUT it may show where there was a found monument (property marker) and give you something to go on/look for. For instance ‘Found I.P.’ (Iron Pin, rebar) or a cross chiseled into the sidewalk.
Liberal, Up to 6 years ago I used to live in Cincinnati but retired to Florida. I think you are OK to send the letter to your neighbors then proceed with your replacement plans. But what do I know? Remember when common law marriages were legal? Sometimes depending on how long someone else has been using something it becomes theirs. Laws vary from state to state. Best check with an attorney.
Phu Cat