Any solution to this needs to be balanced against the workaround of "just let the user learn this once and then they will know subsequently to always confirm the boundaries by scrolling". I don't feel like this is such a pervasive problem (that a level happen to of a particular size, and also have elements obscured but also not obvious that something is getting cut off), so the bar for an acceptable solution should be set higher accordingly. Frankly, it seems like "survey the entire level, making sure you have indeed seen the entire level by scrolling" is an obvious good practice that should be learned early and become second nature, and something you'd generally want to do as one of the first steps of level solving. (Disclaimer: I haven't had the chance to watch the video yet.)
One possibility could be to display flashing scrolling indicators (like little arrows) near the edges of the screen, for the first few seconds or so after the level has started, and then off afterwards (so it doesn't get too distracting). You'd probably also want to avoid doing this on level restarts and so forth to further minimize the distracting aspect. Maybe you can only enable this based on the level size being close to the screen size, although it may then become confusing why the indicators aren't always shown even when scrolling is possible.
Another idea is to display some sort of screen transition when the level starts, where for levels where scrolling is possible, we first display the level slightly zoomed out, and the transition is to zoom into the default zoom level, thus hinting that the level is scrollable. Since it's purely a transition and not the final zoom level, it's okay for pixels to be slightly obscured (ie. blurred) due to zoom. I haven't quite decided if this is better or worse than the flashing scroll indicator idea above. I do know Simon will probably at least object to the time-wasting nature of screen transitions,

and I will admit that this seems more work to implement than the flashing arrows above, for something that's not clearly better.