I like Aeroheads. If the braking surface is in good shape and the rim isn't twisted or bent once it's unlaced, it's probably worth re-lacing. I like DT Competition spokes myself. Wheelsmith makes a similar double-butted spoke that's nice too.

I've re-laced old wheels before when the hubs and rims were still good, but the nipples and spokes were shot. It was worth the effort.