Realistic water paths on randomly generated terrains

Are any of you familiar with DiamondSquare algorythims? I started to use these last summer to create beautifull randomly generated terrains (in my opinion these give the most natural looking shapes to random terrains).
www.youtube.com/watch?v=9HJKrctqIJI

I implemented this for terrains in 3DGS and with help from EvilSOB and JibbSmart I learned to write shaders in order to texture my massive randomly generated terrains at runtime.
www.youtube.com/watch?v=gjGJeNkAO3M

Currently I am back to this idea, but my game has changed from terrains to tile-based (thanks to Superku, sivan, and Uhrwerk for dynamic array allocation) because I find this approach easier for pathfinding, line-of-sight, creating random buildings/dungeons, etc... So my new "terrains" are made out of cubes/tiles and look like this:

*No texturing has been implemented yet (still working on a new shader) so they seem very flat, but believe me they are not. They are just massive (2048,2048 tiles). Each cube is "only" 32 (each edge) in size, but the map's heights range from zero to 2048. So believe me there is a lot of variation in the terrain even though it is not aparrent from so far away.

Now I am tackling a new problem... Creating realistic river paths. I do not want any code, what I am stuck with is the logic.
With the heightmap that this algorythim produces it is easy to create seas, oceans, and sea-level lakes. All I do is choose a height I want the sea level to be, label all the tiles at that level or below as "water texture" tiles, and raise them all to the chosen sea-level height.
The problem now is to create rivers and their origins (above sea-level lakes). I cannot place these lakes and rivers randomly on the heightmap because they look completely wrong if they dont look like they could flow in those directions according to the terrain inclination.

So I know I have to use the height data to create them, but I am stuck on the logic I would need to implement...
How would I decide where to place the origin of a lake?
How would I decide to what height the lake covers (what tiles to label as "water texture")?
How should I decide how the river should extend?
How would I decide where the limits are that differentiate the lakes from their rivers so I know which tiles (lake tiles) I have to raise and to what height?
All this using my height data and withough flooding the whole level...

Any ideas on how to approach this problem are welcome

Odd idea to get at least a realitic river track:
Place a PhysX sphere at the source of your river and let it roll down into the valley.
Track its position into an array and you got a path. Now lower the terrain along this path.

Not really a viable option for me.
Where would I place the ball? If it was at where the lake should be, I have not yet created the lake or determined its size and filled it up, so it would fall down into where the lake would be (an empty valley). Also, remember these are cubes/tiles, not actually terrain, so they are flat on the top, the ball would not actually move.
But even if all those issues got resolved, this is a 2048x2048 size map. Those are waaaaay too many entities to load (I only load large portions of the map for test purposes to see what it looks like, but at 3 fps), it would take way too long to do this at runtime for the player. Even if it were a small map that had 512 fps this aproach is too slow, but considering doing this at 3 or less fps is impossible.

I would prefer a solution programmed myself, not using somebody else's (physX) algorythim. And I am looking for game logic that I can program myself to do the calculation mathematically on my height data withought loading the level. which would be much faster, virtually instantaneous (in only 1 frame, even though it might be a relatively slow frame).

I actually never load the level, I use a FOV+LOS algorythm to only load a relatively small amount of tiles visible around the player. And I dont want to load all of them for my river/lake calculations either. The amount of tiles (4.2 million only counting the ground tiles) is crazy!

EDIT:
fov= field of view
los= line of sight

Even though I didnt like the physX approach, thinking about the ball you said pushed my mind in the direction to the solution to my rivers!
And analyzing how that would be a problem because it would fall into the vallys for the lakes gave me a great idea for the lakes and borders between lakes and rivers!
So even though I am not going to use PhysX, thanks alot for pushing me in the right direction!

Even when discarding ideas, having someone else take a look at problems from the outside always brings a fresh point of view when I am stuck! Never discard a concept you dont like before considering ramifications of that idea!

Here you go: http://bigbadwofl.blogspot.de/2013/02/random-river-generation.html