We've advanced from the old days. In the old days the downstreamer or downwinder people had no rights. Nowadays the coal bed methane people can't salinate your water without permission.
If it rains in Wyoming you can pump out more water and get more depressurised methane, but if it doesn't rain the pumps get shut down.
What stops the CBM producers from re-injecting the brine elsewhere in the bed?
It doubles the cost of the coal bed methane. Dumping it into streams requires one well and pump. Pumping it back down to the a saline aquifer someplace else requires two wells and pumps.
If you have to pump it down, the pressure would make the production well artesian, no?  And if you have to pump it up, the pressure would be less than the gravity head and the brine could be allowed to flow by its own weight.

That just doesn't add up.

That's correct. The pump is required to overcome friction losses of moving the water through the coal cleats. The friction loss in the well and the degasifier are much lower and hardly count. It's moving the brine through the coal that takes the power.
Of course, evey well is different.
The PDF I linked mentioned that the pressure in the seam has to be dropped to the point where the methane comes out.  This appears to require at least some water to be removed from the seam and placed elsewhere, for the duration of the production operation.

Pumping oxygen and steam down an injection well and drawing F-T synthesis gas (plus a lot of raw hydrocarbons) from another would appear to be a possibility once the seams have been dewatered.  I'm rather surprised that the British haven't been doing this with some of their deep coal and undersea coal; they're facing a serious crisis with the decline of North Sea oil and gas.  On the other hand, if they burn out the seams near shore, the land above subsides... right into the sea.

Some British mines ran more than five miles out to sea and mined out the coal in what is known as a longwall system.  This allows the roof to collapse after the coal is removed.  But the roof will only break to about one-and-a-half times the seam height above the coal. (The broken rock bulks up as it breaks and fills up the hole).  Above that the rock has the flexibility to bend a bit, and does not break.  This the breaks don't go to the sea bed, and the sea doesn't rush in, providing they are deep enough below it.
Reinjection is listed as an option here, though I don't see any details about the pluses and minuses.