Recently I installed the latest Skype for Linux (126.96.36.199) on my both systems: Fedora 8 and Kubuntu 7.04. I was surprised because the video calls really work. We talked with one of my friends about 40 minutes (he uses Windows). The quality of sound and picture is good (we both have DSL Internet connection). Not sure how it’ll be for dial-up.
Currently I cannot test Skype with video on Nokia Internet Tablet. Because my N810 isn’t shipped yet from UK. Also I’m not sure that Skype development team built that version for Maemo.