Since the first introduction of the landing obligation (a.k.a. Discard ban) in 2015, the EU Mediterranean fisheries are facing some unforeseen challenges. The demersal bottom trawl fisheries, being the most significant contributors to the so-called 'discard problem', are confronted with the greatest challenges. Data from the Italian and the Greek fleet, spanning over two decades (1995–2015), were analysed with the intention of revealing the diversity and heterogeneity of the discard problem, especially for regulated species. Species composition of discards, as well as discarding rates, were shown to be irregular, fluctuating among areas, depth strata, seasons and years. Although fish dominated the discarded gross catch in weight, benthic invertebrates (other than commercial cephalopods and crustaceans) were the taxa discarded almost exclusively. The established minimum conservation reference size was largely ignored by fishers. From a management point of view, the present investigation suggests that the recently established Discard Management Plans lack scientific evidence (given the high intrinsic variability of the parameters and confusion regarding the rules) and provide exemptions from the landing obligation that will in practice allow the average Mediterranean bottom trawl vessel to continue business as usual. Moreover, detecting if these rules are actually respected is an almost impossible task for the Mediterranean control and enforcement authorities. Incentivizing the adoption of fishing technologies and practices that reduce pre-harvest mortality and post-harvest discards, while avoiding damage to sensitive marine species and habitats, seems the only way to move forward, rather than dealing with the problem after it has occurred.