The theatrical cut of “Blood Simple” was released on VHS (I would assume it was on laser disc but not sure). There was a DVD in R2 which restored some of the cut footage, but not all.
Wes Craven’s (terrible) “Chiller” was released on a DVD which looked transferred from a VHS and was heavily cut. There was a German VHS release which was longer, though possibly still not uncut.
“Hearts of Darkness”, the documentary of the making of “Apocalypse Now”, supposedly had a few small cuts made before Coppola would allow it to be released on DVD. The only specific references I have seen are that one reference to Harvey Keitel was cut, and Coppola singing “Anything Goes”. I’m hoping other people know more about this one.
“Ishtar” might count – it’s only ever been officially released on DVD/Blu as a slightly shortened director’s cut, but technically the theatrical cut was pressed and a few copies trickled out even though the release was cancelled before the official release date.
“The Muppet Movie” had a longer theatrical cut in the UK, released on VHS and nowhere else.
William Friedkin’s “Rampage” has never been released on DVD in region 1; the European version has had a DVD release, but the US cut is significantly different – I don’t know the differences, but I’m sure there’s some extra footage to qualify for this list. It was released on VHS, not sure of the LD status.
Oliver Stone’s “Seizure” - DVD and Blu are the US PG cut, but there was a longer “R-rated” cut. There is a German VHS release, but according to movie-censorship.com it is very rare and might not be entirely uncut, though it seems like all they have to reference the what is missing.
The unrated cut of Spike Lee’s “She’s Gotta Have It” was only ever released on a Criterion laserdisc; supposedly, they’re working on a Bluray of it.
Also, the “German cut” of “Psycho” is now being released on Blu-ray in a German box set, and the unrated cut of “Candyman” is being released by Shout Factory and Arrow, so those can be removed.
Robert Altman’s “California Split” was cut for the DVD, but I’m not sure whether it was ever released in any format prior to that, so I don’t know if that would count.