Euhm ja, frames zijn niet echt aangeraden omwille dat zelfs recente browsers ze niet goed weergeven, idem dito als iframes.
Zoals al aangegeven heb je probleem met externe links vanuit zoekrobots. (Alhoewel dit kan opgelost worden via Javascript)
Tabellen zijn meer aangeraden als je niet echt iets van css afweet of als het echt heel ingewikkelde constructies zijn, waarschijnlijk niet van toepassing. Gelijkhoe ik zou u tabellen aanraden want zo'n (ruwe schatting) 85% van de site zijn nog altijd via dit principe gebouwd. Het is inderdaad niet zo heel officiëel volgens het W3C, maar iedereen kan het zien zoals het moet
Als je echt wil mikken op het updaten van je sites kan je ook php gaan toepassen waarin je de header van je site in een apparte file zet en die heel de tijd laat includen aan de top van je pagina (idem dito voor footers ook)