I don't think any service can claim to be 100% secure from NSA spying. Are we forgetting the claims that the submarine USS Jimmy Carter is used to tap into under sea fiber optic cables to intercept traffic from numerous web services and communications? Considering military technology is most likely 5 to 10 years ahead of civilian technology, we can't assume anything is secure or private any more. In computing power years, 5 years is a long time to research, test and refine hardware capable of breaking supposedly secure encryption schemes.
So while some startups might claim to be NSA snooping free, they don't control the traffic while in transit, it's that middle-layer that's free game for the NSA to tap into and store without anyone being any wiser.
Having said that I have seen tonnes of services start to capitalise on the whole NSA fiasco, namely Duck Duck Go and their billboard ads propping themselves up as a secure Google alternative. And while they might not store searches, that doesn't stop the Government from doing it...