pianist718,
1. Your designers were lying when they made this statement: "as per the internet standards all websites are designed at a fixed pixel size of 780 pixels". There is no such "internet standard". I say this AND i design most of my sites to be a fixed width of 780 pixels.
2. Don't redo the site. This
http://www.thecounter.com/stats/2005/September/res.php will tell you that number of 800x600 screens is declining and you can probably ignore them.
,dave