THE ABYSS (released 1989/directed by James Cameron)
Teaser Trailer - http://www.youtube.com/watch?v=beNm2xj84Fs
Theatrical Trailer - http://www.youtube.com/watch?v=M3fFrVA-dh4
The superior, extended 'Special Edition' version was eventually released in 1993 on DVD, but didn't get a 'theatrical' release or trailer anywhere, as far as I'm aware, unfortunately...