We study the elasticity of fibrous materials composed of generalized stiff polymers. It is shown that, in contrast to cellular foam-like structures, affine strain fields are generically unstable. Instead, a subtle interplay between the architecture of the network and the elastic properties of its building blocks leads to intriguing mechanical properties with intermediate asymptotic scaling regimes. We present exhaustive numerical studies based on a finite element method complemented by scaling arguments.