High Res Terrain

I need to render a high resolution terrain map that has a color associated with each vertex. My problem is that when I get around 800x800 vertices (640,000) the rendereing slows down way too much. My data is atored in a regular grid and I am generating triangle strips along one dimension. I can’t use LOD because I need to color each vertex.
Is there a way to reduce the load on the renderer while maintaining the ability to color all of the verticies? Texture maps aren’t such a great idea because the colors are generated dynamically and I’d have to store hundreds of them in memory.

how are you storing your vertex data?
if you arent using vbos those could give you a performance boost… but btw rendering an 800x800 mesh will still be quite expensive. im just writing a terrain engine and i did implement lod in order to get satisfactoring results (4056x4056 heightmaps arent a problem)… maybe you can generate the textures that will represent the vertex color in the lower detail versions on the fly and then map them onto the terrain…

hmmm… 640k? so there shouldnt be more than maybe a 4th visible at any time and 320k triangles shouldnt be that bad (for modern cards and depending on what you need it for). you ARE applying frustum culling and dont just brute force render absolutely everything?

also, if you say you use strip in one dimension, do you have something like
for (1-800) drawstrip();

please say no, the cost of hundreds of draw-calls will kill your speed a lot more than sending a few more indices. meaning: you hopefully use indexed vertex arrays (or better: buffers) and dont handfeed opengl with glbegin-glend calls?