I don't think you're too paranoid. In this day and age, we have to worry about the bad guys, but I also have to worry about two different legal systems with different privacy rules since most backup services would move my data across a border.

The first on-line system I used allowed me to store the data on another computer, but use the internet to get there. I liked not worrying about who had access to the other computer. That service shut down. It was owned by a company I recognized from the early DOS days.

I now use Jungle Disk. First positive is the data was stored on Amazon's computers. At least recognizing the company is comforting. Second, a guy named Steve Gibson raved about the security built into this product. He claimed that Amazon could not get into the data, even if they seriously tried. Here's a link to the interview he did with a Jungle Disk guy. It's quite wordy, but the meat is closer to the bottom.

If you haven't heard of Steve Gibson, he developed a program years ago called Spin Rite. He's a hard core techie. He has gone on lots of rants against companies like Microsoft when he felt they were doing things that weren't secure. If there is one person in the world I trust to make a security judgment call, it's him.

So yes, I was worried about security, but I'm satisfied currently.