I don't know if this counts, but the algorithm with the worst complexity that I've ever implemented was Tarski's algorithm for quantifier elimination in real closed fields
To explain what I mean by an algorithm having a bad complexity, here's an explanation: The complexity class O(2^N) is called EXPTIME. The complexity class The complexity class O(2^(2^N)) is called DEXPTIME or 2-EXPTIME. You can similarly define 3-EXPTIME, and so on. The union of the class n-EXPTIME for all finite integers n is known as ELEMENTARY.
If N is the number of quantifiers to be eliminated, Tarski's algorithm in the class NONELEMENTARY. I'm just going to let that sink in for a moment.
To be fair to Tarski, his algorithm was an existence proof and DEXPTIME algorithms to solve the problem are now known. However, Tarski's algorithm is much easier to implement, and even though it is not feasible to run it on any problem where N>1, it works just fine on problems where N=1. That's all I needed to solve the problem that I needed to solve at the time.EDIT
By the way, if you're curious about what the problem is, and don't care to read a monograph to find out, here's the elevator pitch version.
So you should know that the theory of Peano arithmetic (natural numbers with addition and multiplication) is undecidable, as proven by Gödel. What you may not know (but probably aren't surprised to learn) is that if you remove multiplication, the theory (which is the theory of Presburger arithmetic) is decidable.
What Tarski showed is that the theory of real closed fields (real numbers with all the field operations, both equality and inequality) is decidable. This seems weird, because it seems like real numbers should be a superset of the integers. But the reals don't have an equivalent of things like prime numbers. If it helps, consider that rational or real linear programming is much easier to solve than integer linear programming. It's the discrete nature of the integers which makes the problem harder.
In fact, Tarski showed that real closed fields have an even stronger property: quantifier elimination. If you have a statement which includes a quantifier, then it can be converted into an equivalent statement which doesn't have that quantifier.
For example, consider the statement:
∃ x. a x2 + b x + c = 0
This is equivalent to the following statement, which doesn't contain the existential quantifier:
(a = 0 ∧ b = 0 ∧ c = 0) ∨ (a = 0 ∧ b ≠ 0) ∨ (a ≠ 0 ∧ b2 > 4ac)
Tarski's algorithm performs this transformation.