Wikipedia 404s, especially using search plugin

When I use the Wikipedia search plugin I almost always get a 404 with https-everywhere activated.

I'll get something like:

---

404 error: File not found The URL you requested was not found.

Did you mean to type http://en.wikipedia.org/wiki/wikipedia/en/wiki/John_K._Samson? You will be automatically redirected there in five seconds.

---

If I follow their redirect it never works (the URL is malformed), but if I reload before the redirect the page loads fine.

Any ideas?

Trac:
Username: macleod199