Ich bevorzuge die Lösung mit position:fixed und dann ein kleines Javascript für den IE, das das Menu für den auch fixiert macht.
Der kleine Teil der IE- Nutzer ohne JS werden es wohl überleben, wenn sie etwas mehr scrollen müssen. Dafür kann man in jedem Browser (der das kann) auch Panning (mittlere Maustaste) verwenden, was mit overflow:auto- Containern nicht möglich ist.