The easiest way to get NE equipment is to fight Geosgaeno at Baaj. Be sure to equip Tidus, Wakka, and Rikku with element-strike weapons. It may take you a few tries (it did for me) but a lot of that battle is based on how lucky you are with Stone/KO Punch. At the end of the battle, there's a pretty good chance he'll drop an NE weapon. Keep in mind it will not have any special name, for example, if you get one for Tidus, it will be the Baroque Sword. I'm really not sure what they are for the other characters, but I assume they're:

Ductile Rod (Y)
Shimmering Blade (A)
Halberd (K)
Variable Mog (L)
Switch Hitter (W)
Devastator (R)

Again, that could be wrong. And, if you don't get it to drop, reset and try again. I know that sounds very very drastic, but the battle isn't THAT hard. Especially since he's weak to all elements.

I also heard a curious rumor that there's an NE weapon (like I described above) in the Djose inn, next to the temple. Can anyone confirm this for me?