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.