They need the email address that you used to purchase in order to try and find the registration. So I don't know if you gave them that email address and they can't find any record of it ?
The biggest thing is you have to have given them the correct email address for their search or they aren't going to find a record.
Did you purchase it through the avast web site ?
If so how did you pay ?
If by PayPal there would be another means of tracking down information about the license.
If you used a credit card, again check your records for information on the transaction.
The payment processing (if through the avast web site) would have been handled by Digital River (element 5), so you could also try contacting them.
Pro license enquiries Digital River (Element5)
https://secure.element5.com/esales/impressum.html?.