The Nokia N80 I bought just over 4 years ago also had a front-mounted camera for video calls. Think I tried it once or twice, since when 3G was rolling out in Norway, video calls were free for a period while regular calls were not.

Stig