There must be a reason why they are confident current algorithms will have a hard time. The article says it works by playing speech backwards so any basic filter will also significantly distort the speech part since I assume the "noise" will occupy similar bands. Subtractive techniques probably won't work either because the noise will likely be highly varying.

But perhaps if one could learn two sparse representations that incorporated phase information for backwards and forwards speech using matrix factorization - it might work as a method for removing recaptcha noise. This idea is so simple though, I assume someone tried it and it doesn't work well.