で、今書いてるdeflateのコードで言うならば、渡すデータがバイトの境界をまたぐかまたがないかで、Either BitArray ByteStringみたいなデータ構造でLeftかRightかを渡すようにしておいて、受け取る側では
Right bs <- get
みたいな形で、「人間はこれが失敗しないことを知っている」というコードの書きかたをするというのが、ひとつの妥協点かな、と。
さらに進めると、前段と後段のあいだに、Either BitArray ByteStringを受け取って、ByteStringを渡すみたいな処理を入れておいて、もしLeftが来たらエラーをthrowするようにするのもありかもしれない。