As well as the way they phrase their reasons for dow'ing you, (just like you put it) there is also a big, red, capitalised BACKSTABBED written somewhere in my experience.
My personal answer to your question, how often does a backstab happen on higher level, is all the time. If they "covet your lands", you will get backstabbed, dow'd, denounced, hated and voodoo dolled no matter what. It's just a matter of (not much) time. If you have a weak army it'll be sooner, if you have a large army it'll be a little later with the pathetic "I know I don't have a chance" play. Added to the fact the AI can pump out 10+ units for your 2, make them count. I wish I had a screen from a game I played where the (thankfully friendly at the time) Aztecs had about 50 units passing through my territory in the "iron" stage of the early game. Though they were mostly slingers, and when he did dow me eventually I had my companion cav. mop them up. Still... 50 units that early!
I play immortal. Never win. Ever. But the one below (emperor?) I find that although it is difficult at start I can eventually overcome and get well ahead. If you can hold on and survive the initial round of backstabbing attacks you could be in a very good position via peace deals to pull ahead of the pack (they usually give you most everything they have if you cripple them). Use these resources and GPT to prepare for the next backstab.
Advice I give, but have been unable to follow myself. Soon enough. Immortal, marathon is my preference. Damned hard for me.