Regarding the fact that the professors whose CV's you looked at didn't have publications before grad school - bear in mind that they got their Phd's two decades or more ago. The amount of research experience and the number of papers published by undergrads in general may very well have gone up in the meanwhile. So while I doubt that publishing a paper is critical to getting into a good Phd program, I wouldn't be surprised if it is weighted more heavily today than in the past.
Other people here will probably be able to give you a much more informed opinion on this.
