Interesting points. I wonder if giving the customer visibility into events like "you data was successfully removed from X" would make a difference? Similar to peeking at your Spam folder now and again to see that it is working for you.

Also about the market size I imagine the market is just US? It seems other places, at leas Europe anyway has better laws to protect against these kinds of invasive services.