In NTSC land, 480 visible lines is the norm (525 total, the rest blanked or used for sync time). In PAL land, that numer is higher (576 visible and 625 total IIRC, but I'm in NTSC land so look that up). NTSC spec would call for 59.94Hz interlaced, PAL would use 50Hz. If you have an HDTV or EDTV, it'll probably have a scaler that will enable it to accept other modes, as well. Note that the horizontal resolution is not specified as it is defined by the bandwidth of the signal - 720 is usually taken as the most you'll get out of any TV system. 640x480 could be useful as it gives square pixels on a 4:3 TV.
TV out on a video card will adjust everything for the TV standard you specify (scaling, converting framerates, and interlacing as needed). Using the RGB/VGA output on a SCART input won't do that, but your TV seems to be taking either mode fine: it may have a scaler or it synced up at PAL timings for 800x600 and NTSC timings (apparently most european TVs are dual format?) for 640x480. I know that by default, Windows won't let you use those odd resolutions, but there are applications that will (Powerstip seems popular) or you can take my solution and run Linux

The TV cropping off the edges is normal and is known as overscan. You can compensate for this somewhat on the horizontal sides by increasing the "porches" on the signal (these are the blanked, non-active portions of each scanline) to make the picture narrower. Vertically, there isn't much you can do other than blank some of the lines (thereby decreasing the number of used/visible scanlines) unless your TV has a scaler. You may also be able to get away with adding a few scanlines into the signal (blanked and unusable) to get rid of the overscan, but this can make fixed frequency monitors (like most TVs) very unhappy (and can actually break them). Some TVs may allow you to adjust the overscan in a similar manner to a PC monitor. Apparently european TVs are better in this regard (providing tons of user adjustments) than USA TVs, but I am not experienced with them.