The Domain Name System (DNS) provides a critical service on the Internet: translating host names into IP addresses. Traditional DNS does not provide guarantees about authenticity and origin integrity. DNSSEC, an extension to DNS, improves this by using cryptographic signatures, at the expense of larger response messages. Some of these larger response messages experience fragmentation, and may, as a result of that, be blocked by firewalls. As a consequence, resolvers behind such firewalls will no longer receive complete responses from name servers, leading to certain Internet zones becoming unreachable because no translation into IP addresses can be performed. Our research shows that despite ongoing efforts to educate firewall and resolver administrators, as much as 10 percent of all resolvers suffer from fragmentation-related connectivity issues. Given that some major Internet companies were reluctant to adopt even a technology like IPv6 if it meant that a small percentage of their users would have connectivity issues, it is clear that we cannot rely on resolver/firewall operators alone to tackle this issue. The contribution of this article is that it a) quantifies the severity of these DNSSEC deployment problems, based on extensive measurements at a major National Research and Education Network (NREN) and backed up by validation of these findings at an independent second location, b) proposes two potential solutions at the DNS authoritative name server side, and c) validates both solutions, again based on extensive measurements on the operational network of this major NREN. The article concludes with a recommendation favoring our first solution. The first solution is relatively simple to implement and gives DNS zone operators control over this problem without having to rely on all resolver operators solving the issue.