Sorry to hear you have a case of "boundary bugs." Only one way to deal with single minded "boundary bugs" - sue them for everything under the sun. Get a recommendation for the nastiest local attorney around, hire him or her, and sue you neighbors. Boundary bugs cannot be reasoned with and must be bludgeoned into submission. Also call the police on them for threats and trespassing as warranted.
As you have seen already, boundary line disputes are not fun and I’m sorry you and your neighbor are in this situation. The best advice is to keep a cool head in these situations and if any sort of violence is threatened call the police. Beyond that, as the police officers probably informed you, the property dispute is a civil dispute and there is nothing they can do in that regard.
In determining your property rights you should consider consulting with a real estate attorney. There are many different aspects and caveats to adverse possession and fences are not always indicative of adverse possession. In general terms, in order to establish a claim to property by adverse possession, the claimant must establish open use, continuous use (10 years), exclusive use (keep others out), adverse use (no permission) and notorious use (known to others). Chaplin v. Sanders, 100 Wn. P.2d 853,676 P.2d 431(1984). But as mentioned there are caveats to these claims and this may not begin to scratch the surface as to what may be going on in your situation. As such, you should really consider discussing these issues with an attorney. You have already had a glimpse into how stressful these types of issues can be, and you should also be that they can also be expensive in litigation. A good attorney should be able to assist you in both protecting your rights and your pocket book.
This kind of boundary dispute gets complicated in a hurry. Because of that dynamic, your offer of mediation was an excellent choice. I have litigated this kind of matter when necessary, but find that mediation offers a lot more options for solutions that serve both neighbors' interests. A quiet title action does get expensive when disputed, and usually each party ends up paying their own attorney fees (at least in Washington). There are some exceptions. If your neighbor has intentionally come on to land he knows to be yours and damages the land or permanent structures, he may be liable for triple damages and may have to reimburse you for your attorney fees. See Revised Code of Washington 4.24.630. Remember, though, just because you are entitled to an award of attorney fees does not mean that you will find it easy to collect the money from your neighbor. And in the mean time, you will be paying out of pocket for your attorney.
If your neighbor has removed survey markers, he may be guilty of a gross misdemeanor pursuant to RCW 58.04.015.
It could be very difficult and expensive to determine whether your neighbor has legally acquired the disputed land through adverse possession or some related doctrine. However, if there is no fence in place, the police and code enforcement will often (but not always) defer to a clearly marked survey as the line until a quiet title case determines otherwise. It may be appropriate to use the police and code enforcement to resist your neighbor's efforts to claim the land by building fences or structures. Be sure to consult with an attorney first, though, because you do not want to be liable for triple damages and the neighbor's attorney fees under RCW 4.24.630.
Mediation can offer a range of solutions to this problem. Even if your neighbor is reluctant to go to mediation now, it may be that he will agree to it once he sees the expense and delay associated with a quiet title suit, and once he finds out (much to his dismay) that code enforcement is never going to permit his uses of the disputed area. All the court can do in this situation is decide where the legal line is (and possibly award damages if there is a trespass claim). In a mediation, you can come to an agreement on the line (see RCW 58.04.007), you can agree to a boundary line adjustment through the local government (this may help with the neighbor's permitting issues), you can agree to a purchase price for the disputed land, you can find out if an easement is more appropriate (in the case that one neighbor cares about use but not ownership), you can deal with the ongoing neighborly relationship (because you've got to live next to this guy for years to come--and you need a gas line in your vehicle), you can deal with pressing or dropping criminal charges, etc.
If you are able to settle this matter in mediation, it is advisable to have an attorney advise you in the process to make sure all related issues are also addressed. For example, a change in the boundary may require compliance with a local ordinance, permission of your mortgage lenders and a review of impact on your title insurance.
People get very protective when it comes to their land, even if it might not be their land, and even if there are only a few inches of land in dispute. I once assisted in a bitterly contested and expensive litigation over about 12 inches of land.
I wish you the best of luck in this dispute.