How about using multiple texture atlases based on which MP screen we're on? We could still pack-and-cache all needed textures and do a (partial?) atlas change on transition from e.g. Home Screen to My Movies.
Commonly used textures (for a given definition of "commonly used") could be packed into the same packfile to ensure they're always available (or alternatively accept textures get put into more than one texture pack).
I guess this could add som lag to screen switching, but most of the time is spent inside a given screen, not on switching between screens, so maybe that's acceptable?
Would require complex and error prone logic to determine the needed textures on different views. Wwe don't want to make any such drastinc changes into MP1 (especially when ATI 2400 with 256MB RAM costs aprox 30e.)
Best way to handle the issue is to optimize the skins itself. For example B3W has many textures loaded into the pakced texture file s that arent used in a single file.