Are there usually consequences for attempted duplicate publication? I recently reviewed a paper for a (reasonably reputable) journal and found that it was already published (verbatim, by the same authors) in another journal (a fake one).
I wrote the following review: "This is a duplicate publication, it appeared two weeks ago in Journal X, here is the link to the copy on Journal X's website."

The timing suggests that they submitted the paper to Journal X around the same time they sent it to us.

In retrospect I should have emailed the editor instead of going through the review site. But anyways, within a day or two the review site showed that the associate editor had seen my review, and the editor listed for the piece changed from the associate editor who was originally assigned to the editor-in-chief.

However, the decision letter that went out to the authors was just a standard rejection letter, with my review appended to the bottom. (The standard rejection letter thanks the author for submitting the piece for consideration and wishes them success in finding another venue to publish it in...)

It seems to me that this is a poor strategy for disincentivizing attempts at duplicate publication; at worst, one risks a rejection if found out.
 (Disregarding for the moment what the consequences would be if they were successful, both papers were published, and then they were found out by someone else.)

I checked the publisher's website and though it specifies clearly (and authors have to certify at the time of submission that the piece is not published or under review somewhere else) that duplicate publications are not permitted, I didn't find any specific details on what the consequences might be.

Is this normal procedure? Do editors usually follow up and try to impose consequences for attempted duplicate publication?

If so:

What kind of consequences are usually imposed for trying to publish the same paper twice, if caught by a journal while in review?
Good question. First of all, as far as I know, there is no penal system in academic publishing. Reputation is everything. (BTW Many of us have made big or small mistakes when we were young and ignorant, learned our lesson, everyone moved on.) Of course, a journal could always shun authors "indefinitely", if they attempt to violate codes of conduct. There is not much more a single publisher can do. In cases like yours, the responsibility falls back entirely on the academic community - whose members are also editors and referees like you - and the control power of one's reputation within it. 

In your particular case, as you said, the editor presumably consulted with the editor-in-chief, which shows it is not a trivial problem to handle, and they decided to proceed as they did. If the journal had rules in place, such as that they would have to refuse future submissions from the same authors, they would inform the authors, but that's obviously not the case. 

You did not specify if those authors are known in your field or obscure. If the editor knows the author personally (which I doubt in your case), the dynamics is different.