残高証明書がなくても相続税申告は可能？

普通預金であれば、相続開始日またはその直前日の通帳に記帳された残高が評価額になりますから残高証明書は不要です。
ただし、定期性預金は相続開始日時点の元金に利息を加えた額が評価額になりますから、利息も証明するように申し出て残高証明書を発行してもらう必要があります。
銀行のミスとはどのようなことか分かりませんが、相続財産に定期性預金があるのであれば、再度、残高証明書を発行してもらってはいかがですか。

このケースでは、行員が「通帳と払戻明細書で足りる」旨の説明をしてることから、
①普通預金は、「通帳を見ると、死亡日までの記帳があり計算可能」、
②定期性預金は、「預入年月日・元本・利率（中間利息払いの有無やマル優の有無等を含む）が各預入番号ごとにわかるので計算可能」
という状況が一般的です。
その場合、残高証明書を取得せずとも計算可能です。
つまるところ、相続税申告には、残高証明書の添付があってもなくても、計算が正しければＯＫと言った方がわかりやすいかもしれないですね。
・貴殿が、自分で申告書の作成をしているケースでは、残高証明書を見て記入する方法がミスしにくいと言えます。
【補足ポイント】
証明書発行の際には、銀行窓口で「残高証明書を死亡日現在で発行してほしいのですが、定期等には死亡日現在の税引後利息を付記してください」と依頼しておくことがポイントになります。
しかしながら、金融機関によっては利息付記サービスをしていない場合もありますので、そのケースでは自力計算することになります。