El problema con los frames es que estructuralmente no tienen sentido. No otorgan información estructural sino apariencia.
Las estructuras mencionadas se pueden usar como frames, si en tus archivos colocas algun 'include' para colocar tu menu (o lo que sea que quieras que se repita en las páginas). Si te ves imposibilitado en usar un 'include' puedes probar con javascript y utilizar document.write. Sin olvidar a los que no tienen el javascript habilitado.
El único navegador en el que creo existen problemas para usar ese tipo de "frames" es con Konqueror , que hasta donde se tienen problemas con la propiedad overflow de CSS. Pero funciona perfectamente en los demás navegadores populares.