When computing with subgroups of a finite symmetric group Sym(n), we generally seek algorithms whose worst-case running time is bounded by a low-degree polynomial in n. However, there are a range of problems where no such algorithms are known, and where the best current methods involve algorithms whose running time may be much worse than this. I'll give an introduction to this class of problems, present results on various special cases where we can recover polynomial running time, and briefly discuss some ongoing work on computing normalisers in the full symmetric group. The new material is joint work with Mun See Chang and Chris Jefferson at St Andrews.