I have battled hair algae many times over the years, at least 6 or 7 times over the last decade. You will not defeat hair algae that has taken hold by reducing nutrients. It's too late for that. Below is my experience with different methods of removal.
Manual removal: This can help keep it in check, but you'll never keep up with it. Scrubbing the rocks will just spread it.
Hydrogen Peroxide: I've used it to spot treat areas in the tank with a small syringe, works ok for small sections but your tank is too far gone. Now if you can take those rocks out, treat with h2o2 and then put the rocks back after a quick rinse then that would work and be highly effective.
Clean up crew: Some people will disagree, but clean up crews are preventative only. I don't care how many snails or hermit crabs you buy, they're not gonna out pace that hair algae growth. A sea hare might work, but I've never had any luck with them. They seem to disappear before they put a dent in it. I did add a couple lettuce nudibranches one time that reproduced like crazy. I had a ton of the little guys and they did out pace the hair algae. Unfortunately as soon as they cleaned an area they let go of the rock and floated around until a pump got them. After a couple weeks I had no hair algae and no lettuce slugs either. I've never tried urchins, but I imagine you would need a ton of them.
Chemicals: When I just didn't have time to fuss with it, I would resort to Algaefix Marine. It works extremely well but it killed my snails. I learned to pull them out and put them in a bucket with an airstone and some nori before using it. No other bad effects. Chemicals are always risky but it's far better than an ugly tank or getting so fed up with the problem that you quit.
Either way, good luck!
