“Completely rids your in-box of spam”? “Eliminate almost all junk e-mail messages”? Those sound like the kind of too-good-to-be-true claims you might expect to see in, say, a new piece of junk e-mail.

But several Internet providers are making this pitch in all seriousness. They might even succeed, but not without forcing major changes in how e-mail works.

This “challenge-response” spam protection departs from previous spam blocking. Instead of assuming that most e-mail is benign, then trying to screen the junk, challenge-response assumes mail from strangers is probably spam. Unknown senders then have to prove that they’re not automated spam relays by passing a simple test on a Web page.

Think of it as the difference between traveling within the United States, unless you’re on a wanted list, the odds are nobody will stop you, and traveling overseas, where you may not necessarily clear passport control. Challenge-response is the “your papers, please” approach to mail reception.

But it works. Spam sent from throwaway or bogus return addresses automatically disappears into the challenge-response trap, since there’s no return address to answer the “prove you’re human” challenge. Even if an actual person sent out the junk mail, only an exceptionally dedicated spammer would fill out a separate challenge-response form for every recipient.

Human senders who authenticate themselves, however, see their messages go through as before.

We tested the offerings of two of the best-known challenge-response systems, and found many kinks left in the system, especially with user-friendliness.

Mailblocks charges $9.95 a year for its mail service, and EarthLink this month began offering challenge-response filtering to its roughly 5 million subscribers.

There were difficulties in start-up, but when sent mail from each test account to the other, both systems worked well: Mailblocks and EarthLink obligingly fired off challenge replies to these test messages.

Several things can go awry in this process. People without Web access can’t reach a challenge Web page, and blind or visually impaired senders can’t get past one.

The stickiest situations involve mail sent by automated programs to willing recipients: mailing lists and legitimate, marketing e-mail.

There have never been any easy cures for spam, and challenge-response isn’t going to be one, either.