If its cleared into your paypal account i think you should pay him, i thought from how you said it that he had paid you by a paypal "echeque" cause he wasnt verified or something.

But of course, if it says into your BANK account clearly on the ebay ad, you still have the right to stick to that.