Since you are both owners, peace is more important than “winning”. Look for a way to make peace.
Can you erect your own fence, blocking the view of theirs?
Well, I’m not sure that painting a fence 40 colors counts as a nuisance under the RCW. I think that’s a heck of a stretch. It would be different if they’d painted a raised middle finger on it or something, but color alone is defensible on the basis of differing tastes. Furthermore, it doesn’t appear that you have proof that they have been harassing you or trespassing on your property; it’s just your word versus theirs, and believe me, a person who will go to the trouble of relocating dog shit will not be above lying about it. So I’m not sure what purpose your letter will ultimately serve, other than pissing them off further or pleasing them, because they’ll know they’re getting to you.
So my suggestion is to be above it, live with what you can live with (including petty annoyances) or have to live with (like what color they paint their fence), and take a stand on the important things, like a loose rottweiler. You already know these people are not above doing obnoxious things just to irritate you – why give them the satisfaction of knowing they are succeeding? Do you really think that will encourange them to stop?
Ignoring it, on the other hand, will lead to one of two results: They will get tired of attempting to annoy you when there’s no indication they’re succeeding, or they will escalate their behavior to something that is actionable, in which case you will have real grounds to pursue them.
Until that point, I’d do nothihg. Why? Because I’ve seen this before: He cuts a tree down so she puts up a fence so he starts curbing his dog on her property so she installs flood lights so he installs a camera . . . . Pretty soon it’s a cold war to rival the U.S./U.S.S.R., and both parties are furious and irrational. Don’t go there. Just don’t. I virtually guarantee that, win or lose, you will live to regret it.
Ignore the stuff you can and object to the rest legally, rationally, and preferably through a lawyer. That’s my advice, though I don’t really expect you to take it.
And IAAL, and practicing in Washington State too, but I am not your lawyer and this post does not constitute legal advice. But I will in closing say that as a lawyer, I never ever send demand letters threatening suit unless I fully intend to file suit if the demand is not met. I’m not sure you have grounds to file the suit you threaten in your letter, so if you’re serious in that threat, definitely talk to a lawyer now. If you’re not serious in that threat, then don’t make it.
On the off chance you’re not going to use a spellchecker, you’ve spelt “damages” wrong.
Jodi,
Thank you for your very reasonable advice. Having cooled down somewhat, I am sure yours is the best approach. I was going to contact an attorney tomorrow, but have decided to wait to see what happens.
Unfortunately, I know as surely as I know my own name that the dogs will be out again. And I certainly will not take that lying down. The Sheriff that came last night said to call animal control EVERY TIME they are out, and I do plan to do that. Nothing is scarier than being chased down the driveway by a 90 lb rottweiler or more upsetting than watching an Akita tear up your cat. This is the kind of stuff we’ve been contending with for years, and under the circumstances, I’d say we’ve been extraordinarily patient, although it doesn’t sound like it. But you’re correct, it’ll either get better or it will get worse, in which case we’ll have something concrete to go after them for.
And Stoid, although I ordinarily really respect your posts, I gotta disagree on this one. It is impossible to make peace with totally selfish and unreasonable people. Bear in mind that they honestly couldn’t understand why we were having a problem. What does that tell you?
No matter how good your letter is, it has a much better chance of having the desired effect if it actually is on an attorney’s letterhead and signed by said individual. Preferably someone with a lot of impressive-sounding partners. It is a relatively cheap (and in my very limited experience) worthwhile option to head off costly and annoying court action.
If you don’t throw trash on their property, yell at them or make any contact other than through appropriately resorting to the police or your attorney, you are not (in my view) “escalating” the situation.
In my city there is currently a dolt wending his way through the court system because his rotts got out (repeatedly) and finally mauled a woman to death. The dolt is a “professional” with advanced degrees. The owners of breeds with a great deal of dangerous potential, when behaving with irrational irresponsibility, need to be brought up short by the appropriate authorities - if not for your sake, for others in your neighborhood (you did say that the dogs can still get out, spite fence or not).
All in faor of not escalating the situation, but you might also want to verify whether or not the fence is built on your property. If it’s on your property and you give them the option of painting it rather than removing it, you’re setting yourself up for an adverse possession claim or some similar nonsense down the road. I have a friend who’s going through something similar with an absentee landlord property owner, except in addition to a fence there’s also an unlawful encroachment by a garage. She had a survey done and the fence is on her property and the garage is built too close to the property line. Just one more potential arrow in your quiver.
(Hijack) Adverse possession…(shiver). Been there, done that, finally decided selling the property was easier than dealing with it (they took nearly 1/4 acre of my property). Fences being cut, fences being moved, fences being mysteriously driven over by large eqiupment, bullet holes appearing in alarming places…little makes people more irrational and violent in property disputes than adverse possession.
If they’re as feral as they sound, asking them to paint their own side of the fence to match yours ‘if they like it so much’ is what they’ll probably do. Best not to provide opportunities you’d rather not see carried through. 
Suing for dimages?
What the hell are those. 
Usual attorney disclaimer.
I agree with most of the suggestions already made. One other place to check for relevant law is local ordinances. If your area is incorporated, try city/village/town hall. Ask for the building and zoning department. If you’re not incorporated, sometimes there are county ordinances that apply.
Here is your million dollar answer. Do not write the letter yourself. It will do nothing but fuel the feud coming from you. Find an Attorney who will write this letter for you. It sounds like you are going to need one eventually anyway, so you might as well get one broken in now. It won’t be all that expensive, and, in the long run, it will probably save you money. There is also a far better chance of avoiding a more costly legal remedy in the future if your neighbor realizes you have sought legal representation and are ready to pursue his childish behavior to adjudication, if necessary.