I strongly believe the best place for a data haven would be inside an orbiting satellite. With the size and cost of storage going down every year, it should be feasible to stick a fair amount of gigs into a payload loftable by Ariane 4 (the -5 blows up too often) or a competitor like Sea Launch. In any case, the advantages of this are manyfold:

  • There's already a communications infrastructure for talking to a satellite. Building one on a reef might cause trouble.
  • Sovereignty is definitely less of a problem up there.
  • It's much harder for someone to physically try to steal the data, especially without being seen.
  • Power is free up there, if you have large enough solar panels.
  • Cooling can be a problem, but passive radiator fins work, and the temperature differential is free, too.
  • If you set up a secure enough communications link (freq, protocol, comm. times, codes etc. known only to you) you can be pretty darn sure that nobody will get to it.
  • If you really, really really wanted to be secure and paranoid, you could use a quantum encryption system to communicate with the satellite. These systems are best devised using lasers, already a viable way to talk to your datacenter without the hassle of fiberoptics. You'd know if someone tapped your communications that way. Also, you could hardwire the satellite to always broadcast a copy of anything it sends out, and send the copy directly to you. Then, you could compare logs and know if someone had managed to nab control of the bird.
  • A paranoid self-destruct option would be quite easy to implement, requiring only a small retrograde thruster and perhaps a small charge to sever the main antenna.
In any case, the real issue would be funding this...and then launching from somewhere that didn't legally 'flag' the spacecraft as its territory. Sea Launch would be ideal for this; as a standard operating procedure they take their payloads out to the middle of the ocean (near the Equator, for maximum efficiency) and launch there. If you were really paranoid, you might deliver the payload to them at sea.

Actually, this is a fairly cool legal and technological problem.