Problems that are NP-complete under randomized or P/poly reductions.
As suggested by Peter, I converted my comment into an answer. 

Valiant-Vazirani Theorem states that if Unique SAT $\in P$ then $NP=RP$. To prove their theorem they showed that the promise problem Unique SAT is $NP$-hard under randomized reductions.

[1] Valiant, Leslie; Vazirani, Vijay. "NP is as easy as detecting unique solutions", Theoretical Computer Science, 47: 85–93