I once had a ticking sound that was caused by the sole rubber of the shoe being cut just a little to big around the back of the cleat support platform inside the sole.
It was just enough so that when I would pull up, the rubber would "pop" over the edge of the support. When it pushed back in on the downstroke it was silent.
I'm not suggesting this is the problem, only that these things can be maddeningly hard to track down and it isn't always the pedal.
Yes, the threads of the pedal should always be greased before installing into the crank. And the clip mechanism of the pedal itself should be lubed. (I just use the same ProLink I use on my chain.)
Training: 2002 Fuji Roubaix Pro (105 triple)
Commuting/Daytripping: 2001 Airborne Carpe Diem (Ultegra/XTR, touring wheels)
Commuting/Touring: 2000 Novara Randonee (Sora/Tiagra/LX, fenders, lights)