Welcome to the forum... Where in VA are you?
Sounds like you have a classic under managed older pond that has become very eutrophic. The biggest question is: What are your goals for this pond? Once those goals are determined, then a plan of action can be taken. Ponds are holes into which money is thrown. Particularly if you want them to meet your expectations... The cost you are being quoted, it's hard to say what is reasonable and what isn't. If you live near by, I may be able to come over and give you some on scene advice. I don't own a pond management company and won't charge you a penny. I can at least get you started with some ideas and what you can expect to pay to accomplish your goals.
