even with vertex shaders you would still have the problem that straight lines are not curvy enough.

The first gpu manufacturer that realises that lines are realy straight curves will make alot of $$$.

If displacement mapping existed in OpenGL, you could combine vertex programs with it and get a 100% correct fish-eye view.

If you want to project to a curve, a bad solution would be to grab the screen and project it on a texture over a distorted quad. It is not physically correct, but looks fine for a demo, for instance.

Well, use heavy tesselation on models that are close to the camera, the line effect will be reduced

How bout rendering the scene to a cubemap, then use the cube map on a quad in ortho mode and use a fragment program to do the proper distortions. Should be fairly fast and 100% accurate.