They can just go along with what other cloud storage providers have been doing all along... that is, "we won't snoop into your phone, because that's yours. but if you upload photos to iCloud, onto OUR servers, then we reserve the right to scan for images in CP database.."
And I think most people will be perfectly fine with that idea.
Just like you sign away some rights and accept risk when you decide to store items in physical storage facility, same thing will happen when you use iCloud.
Look at Google trends data for the search term “Apple.” It spikes every September by like 70% for a week.
I can guarantee you, every average joe learning about the new iPhone from mainstream media, is going to hear a sound byte about this fiasco as well.
I’ll be surprised if this program isn’t dead within 2 months.