The data controller is obliged to use “all reasonable measures to verify the identity” of the person exercising their data subject rights (GDPR, Recital 64). That sentence has caused a lot of confusion:
- “all reasonable”: does this mean all measures the controller can be reasonably burdened with, or all measures that are necessary for identifying the data subject with reasonable certainty?
- “identity”: does that mean the identity of a natural person, or just a check that the person exercising their data subjects rights is identical with the data subject?
So depending on how the company interprets this, there is a lot of leeway regarding which info may be requested from you. In general, being able to log in to the service should be all that is necessary (compare also Recital 57).
Note that the company doesn't just have to satisfy your data subject rights, they also have to protect your data against unauthorized access. Giving an attacker access just because they control a particular email address might not be secure enough (but is in practice because the attacker could use a password-reset functionality to get the full credentials anyway).
You do not lose your data subject rights if you used pseudonymous/fake data: the service may still contain other personal data regarding you, for example usage profiles. You are still a data subject. Pseudonyms can also be identifying data, e.g. Art 4(1) calls online handles out as a kind of personal data. However, this does lead to complications with companies that interpret identity verification as ensuring that the person making a request is a particular natural person.
If the controller isn't sure about your identity, they can request additional information (Art 12(6)). If the data subject cannot be identified, the data subject rights do not apply (Art 11(2)). However, that describes a subtly different scenario: that the data held by the controller lacks identifying data.
You do have a right to access and a right to rectification (correcting the data they hold about you). However, they require the exact same identity verification as the right to erasure.
That you were underage at the time of account creation is likely irrelevant now, if the data in the account doesn't indicate your true age. Unless the subject matter of the online service makes an age restriction necessary, the relevant age limits are 13-16 years (Art 8 GDPR, subject to EU member state laws) or 13 years (COPPA, U.S.).
If you believe you have provided all data that is reasonably necessary to verify your identity and your data subject rights are denied to you, you can issue a complaint with your local data protection authority. In Germany, each Bundesland has their own Datenschutzbeauftragte agency.
Below, relevant GDPR excerpts used in this answer. “Erasure” is Art 17 but Art 12 covers modalities for exercise of data subject rights. Recitals are explanatory but not normative.
Art 12(6): Without prejudice to Article 11, where the controller has reasonable doubts concerning the identity of the natural person making the request referred to in Articles 15 to 21, the controller may request the provision of additional information necessary to confirm the identity of the data subject.
Art 11(2): Where […] the controller is able to demonstrate that it is not in a position to identify the data subject, […] Articles 15 to 20 shall not apply except where the data subject, for the purpose of exercising his or her rights under those articles, provides additional information enabling his or her identification.
Recital 57: Identification should include the digital identification of a data subject, for example through authentication mechanism such as the same credentials, used by the data subject to log-in to the on-line service offered by the data controller.
Recital 64: The controller should use all reasonable measures to verify the identity of a data subject who requests access, in particular in the context of online services and online identifiers.
