This is a tough question. I would say it does not sound very natural. 1. Using a phrase like "Very often" or Quite often" at the beginning of the sentence sounds strange, unless perhaps it is written in a book or something, but "Quite often" sound better in that scenario ("Quite often he'd find himself in peculiar situations."). 2. It doesn't sound weird enough to say it is completely wrong, but I would use "Usually" or "Generally" or just "Often" or even "Oftentimes," which is super old-school. 3. I would, however, prefer to change the sentence around and say, "I often can't fall asleep when he falls asleep." Note: I would say it doesn't sound natural to use "very often" in this sentence either. We don't use "very often" very often (unless we are saying it at the end of a phrase/sentence as in this sentence). This is almost the only construct of a sentence where I would use "very often." I don't go to the store often/very often. I don't go to the store that often. (more colloquial). Interesting topic. Hope this helps!

Maybe it is Commonwealth English rather than American English, and perhaps a little old-fashioned, but I have no problem with "very often" as used in this sentence.

This is as natural as any other form .