How to pay tds if the opp.party's pan status is showing "deleted"

TAKE A XEROX OF COPY OF HIS PAN NO.  If the property is registered then see the agreement. it is written in the agreement.

You need to check the agreement. Whatever is given in the agreement, consider that as final and pay the tds amount accordingly.

In absence of PAN, tds is to be deducted @ 20%. Also on a safer side, get a letter confirming about his deletion of pan. 

How did he enter into a transaction without holding a pan?

Are the seller details matching with the new pan on it website and agreement? If yes then no issues. But if no, then you may have to report it to your ITO also

He needs to contact his AO about histatus of pan deletion and its reason. Meanwhile you can approach your AO making an application for condonation of delay in filing tds return because of the said reason. Approach the AO at the earliest. 

The AO will condone the delay because this is a genuine reason 

No you may land up in further more complications. It is never ITO who will correct on its own motion. You would then have to approach for correction and then it will be rectified after a few days, which might be even more tedious. Also the tax credit would be given to someone else's pan (third party). So the procedure that I suggested will work. You can approach your AO and narrate the reason with an application for condonation of delay. You will be on a safer side having something to state that you were not a party to default. And will be saved from tds interest and penalty provisions. Do not fail to take an acknowledgement from AO for the said reason.