I actually spotted a factory sealed copy of the '04 Trilogy in the wild tonight. It was at an indy record shop that has a DVD section, tucked away in a glass case with some other box sets of recent vintage. It was less than sixty bucks.
I checked their used DVD section while I was at it, and only saw two copies of the prequels.