First - I am directly connecting via HDMI on both the computer and the tv.
Second - The video driver I am using is an integrated ATI Radeon HD 4200 but I don't think the software is scaling the image down - but it might be. The max resolution per the catalyst software available is 1280 x 720.
Your TV is limited to 720P (1280x720) as your post stated. Make sure that you adjust your video resolution to 1280x720 when you connect it through HDMI. Most and early generation HDTV are set to default native resolution when connected to PC via VGA & DVI. Thats the reason the video is crisp when you using VGA. The TV runs at default native resolution.
Two things to do after HDMI connection:
1) Adjust your resolution to 1280x720 (720P native resolution). This will make your video crisp.
2) Adjust the Video Card Scaling feature to fit the desktop to the TV screen.