Talk to a surveyor or lawyer familiar with property issues.  When you say "given free and clear title" do you mean it was guaranteed by a title company?

My understanding (that is a warning!) is if you have it surveyed and the neighbor disputes it the only solution is go to court and find a mutually agreeable surveyor to do it again.