Ritengo che non ci sia nulla di grave, soprattutto proprio nulla die "atroce".
Considera che la tua richiesta è per residenza (non per matrimonio), quindi, il fatto che tu sia sposato o no con la tua compagna (quindi solo convivente) non conta nulla.
Per quanto riguarda la prova della residenza, questa si fa con autocertificazione (che ovviamente, deve corrispondere al certificato storico di residenza che la questura si fará inviare dall'anagrafe). In csao di dubbi, cioé se non ti ricordi più da quando a quando eri residente e dove, vai all'anagrafe e chiedi all'ufficiale di consultare il computer e darti i dati esatti (potresti anche farti emettere un certificato storico di residenza, ma ti costerebbe 15 euro di bollo).
Per finire, penso che la questura dovrá ben sapere a partire da quale data la legge italiana ha cominciato a prevedere il permesso di soggiorno per i minori. In tutti i casi, per il fatto che tu sia stato legalmente o illegalmente residente prima del compimento dei 18 anni, sono i tuoi genitori i responsabili, non tu. A te si puó imputare solo la legalitá rispettivamente l'illegalitá della tua permanenza da maggiorenne.