The quality of commercially available extra-virgin olive oils (VOOs) of different chemical compositions was evaluated as a function of storage (12 months), simulating market storage conditions, to find reliable and early markers of the virgin olive oil (VOOs) quality status in the market. By applying a D-optimal design using the Most Descriptive Compound (MDC) algorithm, 20 virgin olive oils were selected. The initial concentrations of oleic acid, hydrophilic phenols, and α-tocopherol in the 20 VOOs ranged from 58.2 to 80.5%, 186.7 to 1003.2 mg/kg, and 170.7–300.6 mg/kg, respectively. K270, ∆K, (E, E)-2.4-decadienal and (E)-2-decenal, and the oxidative form of the oleuropein aglycon (3,4-DHPEA-EA-OX) reflected the VOO quality status well, with 3,4-DHPEA-EA-OX being the most relevant and quick index for simple monitoring of the “extra-virgin” commercial shelf-life category. Its HPLC-DAD evaluation is easy because of the different wavelength absorbances of the oxidized and non-oxidized form (3,4-DHPEA-EA), respectively, at 347 and 278 nm.