@Mehdi Gholam, Not necessary that we need a key to sign an application. Using Verisign withour password key is also possible.
I GOT SOLUTION to my problem :
Well, sometimes it works perfectly well and sometimes it just fails for signing also.
Cause of Failure for Verify : Signtool provided by MS doesn't support to verify CA Certificate. Check this @Anthony Nel's resposne
Cause of Failure for Signing : Probably timestamp which doesn't work always. If I provide the same command again, it works perfectly well.
Added the commands in PostBuild also and it does the job well (as I said if 1st time it creates error, build 2nd time and it works).