That's a strange problem and might require tech support.
What version are you using? Are you on a Mac or PC?
Are you using the main computer or the web access?
Do you select "record" when you finish an invoice?
Is there any chance that the invoices were actually deleted by someone?
Do you add the new customer in the add customer section of EI, or just type them into the invoice? The best way is to use the add customer section.
Do you keep printouts of your invoices? Have you done an EI backup that can be restored?