saliendo就好，副动词可以匹配任何时态，不需要画蛇添足再加haber表完成了

有点别扭，可以这样写: saliendo del restaurante, recordó que no pagaba.

Haber是可以用副动词形式的，为了证实准确性，我去语料库里查了下。找到了几个例句和你分享一下：
1. Esto es muy positivo y da mucho apoyo, no habiendo recibido ningún comentario negativo.
2. Se espera que los estudiantes asistan a clase habiendo leído el material que se tratará y que estén preparados para discutirlo.
所以，都是那种类似于英语的独立结构，然后又是过去的过去，用完成形式。
综上所述，我认为habiendo salido是没问题的。
---贴吧极速版 For UWP

接楼上。其实我也很少见。所以我特意去查了下语料库。类似于英语的独立结构，因为一个简单句是不能出现2个或以上变位动词，所以用这种独立结构的形式，来表示在...之前怎么怎么样。你把它拆成两句话就简单了：Él había salido del restaurante. Él recordó que no había pagado.
---贴吧极速版 For UWP