Solving block banded block Toeplitz systems with structured blocks: new algorithms and open problems