The other option is to use dynamic range expansion on the compressed tracks. I bet you'd start to really hear the terrible compression artifacts, though.

Of course, the potentially better solutions are all both CPU-intensive and storage-intensive. The big advantage to replaygain is that it's CPU-intensive, but that can be done beforehand because it stores its data in 4 bytes per track (8 if you use per-track and per-album data).