Robust verification of protocol conversion and arbitration schemes of SoC bridges forms a significant component of the overall SoC verification. Formal verification provides a way to achieve this, but a naive approach often leads to explosion of the state space, and is impractical for most of today's protocols and bridges. This problem is further complicated in the presence of serial protocols, where control and data are mixed together and transactions continue for very great depths. White-box verification is not a feasible solution, since these bridges are often imported or generated from other sources, and internal information is not readily available. In this paper, we propose a black-box and hybrid approach to this problem, by judiciously mixing simulation and formal verification. We illustrate our approach by applying it to two dual stage bridges that perform serial to parallel protocol conversion and vice versa.