I face similar problems with large datasets and have tried a variety of ways to get around it. You don't mention in your post how the data is generated: in my case it normally comes out of a database and I have server-side code (ASP or JSP) to send it back to the Flex client as XML. So far I have worked around the problem by suitably parameterising the SQL calls so as to keep the number of points down, but the time is shortly coming when this will no longer be a feasible option.
Now, what I have been considering is how to do more work on the server to prune down the data. As you rightly say, the display end can't do more than show one point per pixel (though perhaps a flyover hint could say more). I have been thinking about ways to manipulate the XML at the server - conceptually it is not very different to what mapping software does, or deep-zoom type image manipulation, where you have a series of more finely grained responses depending on your level of view. As yet I have not progressed far along this line so the ideas are quite vague just now - but I am convinced that it is at the server end that the work needs to be done.
I had a timeout problem originally with large sets of data returning from the server. I switched from an HTTP request to a RemoteObject and that helped alot. The root of the problem, as far as I can tell, is that Flex doesnt handle large datasets very well (at least not with data retrieval and/or graphing). My application was originally designed and implemented using GTK on Windows. GTK handled plotting of large datasets very well, Flex not well at all.
Limiting calls to the server is something that should be done, so I plan on loading all of the data into the flex app from the server (using remote object). Somehow, I have to find a way to limit the number of points/data_elements in the dataprovider. If I can get the proposed X/Y, then I guess I can do this and only put one of each element at any x/y into the dataprovider. BUT, any time the application is 'zoomed' or resized, I have to recalculate.
I would have hoped that Flex, or someone, had tackled this kind of problem before?
What I have done is a kludge. In the flex app, I am taking my imported data (in my case, around 37,000 is the most I have tried) and had to kludge the plot chart so that it only display one data point within a 5 pixel radius (e.g. if a point is at x:20,y:20, I cannot seem to display anything from x:15,x:15 to x:25,y:25). I still dont have this working totally (I have to load the data, find out which x/y each point would be at, then only put ONE point within a 5 pixel radius into the data provider as I traverse through the data). If I dont do this, FLEX times out. It does not seem to be a function of the number of elements in my dataProvider/arraycollection (ran my app without the graphics and it didnt choke). I played around with the radius factor and anything less than 5 pixels (when attempting to plot as many of the 37,000 as I can) causes Flex to time out. 5 works, as does 6, 7, etc.
I really hope I am not missing some fundamental concept that is causing the timeout problem. I have poured over the documentation and nothing popped out at me.
I also noticed that the CPU on my PC peaks at 100% when the actual rendering of the graphics is done.
So, my only conclusion (with admitted limited experience using Flex) is that Flex cannot handle graphical display of large data sets very well.