What does "paper rejected provisionally" mean?

I've seen language like this before as well, and feel that it is unnecessarily confusing. Usually, what I have found is that it's effectively equivalent to "Major Revision." Here is a good heuristic for distinguishing:

• If they give you a date that they'd like to see the revised version by, then it's equivalent to "Major Revision."
• If they don't give you a date, then you've been rejected, but they really are inviting you to submit a better version when you are ready.

It needs substantial revision in order to possibly become publishable

That's sounds the same as "major revision" to me.

Is "paper rejected provisionally" equivalent to "major revision" ?

You're simply concentrating on the last thing written, not the part about "substantial revision", which is unambiguous. All the "provisional" part is saying is that they're open to re-submission after a big rewrite and are not completely rejecting it (and you). I'd actually consider it as a mildly encouraging choice of words.