Since the OP specifically mentioned "Acetaminophen" and "Naproxen", it's worth mentioning that Acetaminophen is _not_ an NSAID like Ibuprofen, but Naproxen is.

That said, like the OP, I used to also take lots of Ibuprofen for headaches, and unfortunately, Acetaminophen never seemed to work for more than an hour or two max (tested in "isolation" for 7+ days), while Ibuprofen could stop the headache cycle for a day+.