I have never heard of red legs eating them either. I have heard of nudibranchs (berghia), copper banded butterfly fish, and foxfaces (I think).
I have used kalk and Joes Juice to get rid of them with good success. I would also not hesitate to use the hot water method but would be hesitant to try vinegar, lemon juice, or hydrogen peroxide (all of which are said to be quite effective).