Credit for service tax paid on advance payment

Hi all,

When can a service receiver claim cenvat credit for service tax paid on advance payment to service provider. The service provider has not provided any documentary evidence or invoice for the advance received but he had properly discharged his service tax liability for payment to govt within due date.

Can the service receiver claim credit for service tax stated above immediately or only after the receipt of invoice, and under which clause??

Pls reply urgently