How was the special high-contrast cinema release of Se7en created?

It's a technique called silver retention, also known as bleach bypass.

To quote from Cinematography: Theory and Practice : Imagemaking for Cinematographers and Directors:

Deluxe, another film lab with a long history in Hollywood, uses a process called Color Contrast Enhancement (or CCE). CCE raises the contrast, deepens the blacks, and adds grain but still preserves some shadow detail... The amount of silver retained is read with a densitometer centered on 1000nm. According to Deluxe, a pure bleach-bypass that retains 100% of the silver might yield an IR density reading of as much as 240, which translates to four times the amount of silver that would be found in a normal print. With CCE normally processed negative (no special processes) a normal reading at 1000nm might be around 60. With CCE, a typical reading ... might be around 180 to 190 IR. This translates to about 75% silver left in the print, where retention of 100% will not only increase the density of the blacks but of the mid-tones as well. By keeping the amount of silver retention in this range, there will be some desaturation of the color, an increase in grain, and denser blacks, but there will still be some detail in the blacks, unlike in 100% silver retention, where the blacks might block up. CCE was used on the film Seven and many others.

The American Society of Cinematographers have a much more readable summary including an interview with the vice president of technical services at Deluxe (the film lab mentioned above), saying:

CCE is a proprietary process that produces a much higher contrast and adds more grain. When you have more silver, you have a more grainy look and blacker blacks. However, your blacks can also plug up more. With a bleach-bypass, the tones are much duller and more muted, and you have a lot less detail in the shadows. The blacks are very black, but the nuances in the gray are diminished.

The special editions you mention used one of these CCE silver retention process prints, whilst the New Line VHS and DVD releases used the regular theatrical prints.

As to how widespread the releases are, I'm struggling to find a definitive answer on that. A mixture of IMDB and some random forums online of Seven addicts suggest the original cinema release and the Criterion DVDs used it, whilst the New Line VHSs and DVDs were straight from the negatives and thus didn't use silver retention. Apparently blu rays cannot have silver retention performed in the usual manner, and instead it is done digitally - but that the latest blu ray releases are good enough that they efficiently replicate the original silver retention prints.

Unfortunately, all of this is just conjecture and there doesn't seem to be an official word on exactly what uses silver retention and what doesn't.