The easiest, and often very cost-effective way, to arrange for service in another state is through the local sheriff or constable. If you know the county in Virginia where the individual lives or works, you can call the sheriff for that county (you should be able to get their information from a simple internet search) and ask for assistance with service of process. You will need to send them the papers they will need to serve. Also, if you can, send them an affidavit of service form provided to you by the Court for them to fill out and return to you. You will have to pay them a fee, of course. Once they effect service, they will send you the original affidavit of service, which you will need to file with the Court so they know the other party has been properly served.
You should not require an attorney if your petition is pending in the Family Court. Be prepared with as much documentary evidence as you can to prove the child is emancipated, in this case, in the military. Good luck.
Mr. Rosen practices matrimonial and family law in Great, Neck, NY. His response here is not legal advice and does not create an attorney/client relationship. The response is in the form of legal education and is intended to provide general information about the matter in question. Many times the questioner may leave out details which would make the reply unsuitable. You are strongly advised to confer with an attorney in your own state to acquire more information suited to your particular circumstances.