I know Google did, e.g. here's a 2007 story on that: http://www.expertreviews.co.uk/general/108490/google-denies-...

I can't find any explicit denials by Apple, though. Digging through some 2005-2006 news archives, I find Apple denying some specific rumors, but neither confirming nor denying whether they would come out with a phone in general.