Is it possible for the network to stop finding valid blocks? The hashing problem is by design computationally hard, because SHA-256 hashes are for all intents and purposes random strings with no direct link to their inputs, and there's no (known) way to generate a block so that its hash computes to a given output (or, more exactly, satisfies the current difficult criteria). At any given difficulty level, there will only be a certain probability for miners to find a valid block.

Ok. But is there any proof that a valid block will actually exist at a given difficulty level? Is it possible that valid blocks just stop being found if difficulty increases too much? How could the network handle such a situation, if the difficulty level can only change every X blocks?
The simple answer: no.

The not to simple answer: extremely unlikely.

Miners hash an input block, in the hopes of getting a result that satisfies the difficulty requirement, i.e., has a certain number of zeroes in front. Now the possibilities for the miner to vary the input are quite large. There is the 4 byte nonce, there is the order transactions are put into the transaction (for simplicity let's just assume it allows all permutations of the merkle root, 2^256), there's the coinbase in the reward transaction (which also influences the merkle root), there's the timestamp (not that variable but let's say we can vary by two hours => 14 bit) and there's the transaction count (up to 4 byte, that are not independent from the merkle root, but let's assume they are indipendent). So in total we have something in the order of 2^256*2^32*2^32*2^14~=3.49E100 possible inputs to find a block and 2^256~=1.15E77 possible block hashes. (These are all back-of-the-envelope calculation, and probably wrong, but just to give an idea of the scale of this)

Hence we would find ~3.02E23 hash collisions for each hash, and would have to not find a single hash that matches the target. Notice that hash functions are built with the stated goal of making hash collisions really hard (researchers have used super computers for decades to find a single hash collision), and you'll see it is unlikely to ever occur in anyones lifetime.