Ran into the exact same issue when using Parse. I was working on an app that operated primarily through push notifications. The push notification downtime was horrible -- I remember having to get on calls with clients apologizing profusely for the downtime. We were also paying Parse an absurd amount of money for extra reliability, which didn't seem to help much.

I never heard people talking about the difficulty of moving off of Parse, especially in mobile clients that were developed with the Parse SDK. I spent a ridiculous amount of time getting Parse synced with our custom backend so old clients wouldn't break.

Final thing: debuggin. For nearly any issue, a half-assed solution---often not usable in production---by one of their staff was buried deep into their forums. Super painful.