The first pic. I believe is bryopsis. I was able to eliminate it with a two week treatment of fluconazole. If you look closely there are a few strands mixed in with the bryopsis that almost look like a single strand of hair algae. They don't have the "fern look" of the bryopsis..... But it's not hair algae. As you said, this stuff is well rooted and tough to pull off of the rock. It looks like a scraggly beard once it takes off. (pic #2) I found several threads on forums about cladophoropsis and i believe that could be what I have. I have several thick clumps of this stuff established in my rock work. It all started with one frag and a few innocent looking strands on a frag base. I don't feel good about manual removal of algaes of this type because I've read too many times that when small fragments get loose in the water column they settle somewhere else in your rock work and start a new "patch".
In the future I'm going to be a lot more careful about the frags I select and remove and discard as many frag bases I can from new corals.