alright, how about this. The two player game is not hosted on the server, but rather the faster of the the two playing. This way, Clientside randomization is not a problem, as it is only on one computer. The powder toy on the second computer is an editable projection of whats on the other computer.

This would eliminate all the problems talked of above.

almost as fast as normal/ normal, because only the faster computer runs the program, its just that both can edit.

No Problems with clientside randomization, as there is only one simulation.

So i think this solution would work.

don't forget there would be input lag of about 60-100ms from the client user, that is usually only 3or 4 frames though so not a big deal. The bigger issue is with coding.

How about being able to LAN powder (Even wireless normally goes over 50mbs)
Basicly one user sets up a server and listens on a certain port (for this demo it will be 2233)
Then another user presses SEARCH and sends out a message (that won't go past any modems) on port 2233. When the server hears this it sends a reply and the client ends up with a list of all the servers on the LAN.
If I could LAN powder on the boat i take to get to the mainland that would be epic!!!

As for online the best idea would be to allow users to set up there own servers. When you create a server it sends a message to a central database which will keep tabs on all active servers so clients can find them. (there should be a option so people who are just going to give friends their IP can stay hidden).
HOW TO MINIMIZE LAG:
Basicly each game simulates its self and they only cummunicate when someone inserts something.

What if you basicly took your two fps rates, compared them, and slowed the faster one down to the slower one? I don't know how simple or complicated this would be, but it would keep them in sync. Another idea is have the faster computer do all the calculations, and just send an image to the slower one, and he slower one would return any new inputs to the faster one.

Yeah I know, I was saying, basicly make it constant, I don't know if it is possible, but that was the idea.