In my own experience the OpenOrd algorithm did not produce as good layout as I'd liked it to. I tested OpenOrd on a network that had 1-10M nodes and maybe 5-50M edges depending on what filtering was done beforehand. Later I started to use Force Atlas 2 which produces lots of better layout and can handle node sizes (no overlapping).
I've used both VNA and GDF formats. GDF is probably better although the file formats are quite similar. GDF is easy to open with File > Open... in Gephi. CSV files need to be imported which I think is more tedious. Generating GDFs programmatically is also quite easy because edges and nodes are defined on single lines.
For visualizing large networks there are some tools but none to my knowledge that are particularly finished. Seadragon plugin is in Gephi. It renders a large picture and chops it into smaller pieces. Not suitable for extremely large networks as yours.SigmaJS
I've been doing my own visualization for large network myself but the project is still work-in-progress. It is not likely to be complete plugin or anything like that in near future either. However it's possible to render large networks as long as the network fits in the memory. Currently rendering times are also quite slow due to missing optimizations. You can see an example network at http://126.96.36.199/mapper
Spinoff of that project is similar visualization which loads all the node data in a JSON at page load, http://188.8.131.52/mapper/map/pege
. It'd be great to make a generic plugin out of these projects but currently my time is limited for these. Check this Gephi thread for more info, http://forum.gephi.org/viewtopic.php?f=28&t=2314
Another Gepher, solipsy, posted about how to publish large networks on MapBox: http://forum.gephi.org/viewtopic.php?f=28&t=2518&p=8306
. I talked with him over PM on these forums and he seemed interested in helping others with this stuff. I'd be happy to give more information if it's needed. I hope someone can use this procedure to publish their own map.
You may want to send him PM so he gets an email alert about new message at Gephi forums.
Good luck! Let us know if you get any results.