I've given this a try and I'm curious how you're handling the triangulation near the coastline. Not creating points outside the landmass gives triangulations like this:
poisson-edge-problems.jpg
This in turn gives rivers that reach the coastline at very oblique angles. Are you continuing the triangulation beyond the coasts but truncating the triangles? If so, how do you handle altitudes of these triangles? Is there some other solution I've missed?