When applying for PERM, how much stricter it is comparing to requirements for H1B, and how likely is one to get rejected? Do you really have to prove that there aren't many people capable of doing your job, or is it just formality verifying credentials for your qualifications?
Yes you do, no it is not. Many PERM applications get audited (where the DOL people will go through the whole hiring process and will examine the employer's evidence to inability of hiring a US resident). Audits delay the processing by about a year if everything is in order.
Generally, PERM should not be done without a good legal counsel which will ensure that the process is managed properly. But even then, a rejection is possible and the approval is never automatic. It is not unheard of for PERM to be rejected.