In realtà il sistema operativo elimina i file marcandoli come cancellati (quindi sono ancora sul supporto) ed eliminandoli dalla tabella di allocazione file, quindi FAT (File Allocation Table) o MFT (Master File Table): è un po' come se invece di staccare la pagina di un libro si togliesse l'indicazione che la riguarda dall'indice.
Quindi come ti ha già detto Fred, i file sono recuperabili sempre che non siano stati nel frattempo sovrascritti dal altri dati.
Il cestino viene creato di norma direttamente nell'unità dove vengono cancellati i file (nei sistemi con file system NTFS ogni utente ha il suo cestino) e non mi risulta sia un comportamento diversamente configurabile, ma anche io come Fred non ho la certezza che sia o meno possibile modificare le impostazioni di default.