You can copy Fat Lip off your Xbox, extract the songs.dta using Le Fluffie, edit it, and then make a new folder (under song info fixes or w/e) titled "fatlip". If the folder only has a songs.dta it's assumed to be a fix, so the packager will load it.
Just wanted to report that I followed your instructions and it worked, wouhou!
I also got rid of the ö issue in Blue Öyster Cult name but forgot to take care of Maxïmo Park's ï which is also currently turned into ?i. >_<
So I was thinking: "hey, let's do the same for customs I'm in trouble with". Actually, Motörhead's Overkill and songs from Mötley Crüe that I downloaded in C3's database are all having the same trouble with the umlaut. Also, I have some other customs grabbed here and there having trouble with their album name only. Well, so I did the same thing as for Fat Lip and respected the name of each song in the songs.dta. Everything went fine after the cache rebuild and my changes appeared on screen. But as soon as I deleted the "dummy" file, some songs re-sorted badly. All the umlaut issues re-appeared but the songs I had trouble with the album names stayed fine. I don't understand what happens with these umlauts... The encoding parameter was set to latin1 everywhere, so I guess this is not the problem.
Anyway, actually not a RBHP issue (since I edited successfully your files) so I might be off topic but I wanted to report here because I used the dummy/upgrade packager tool to try to solve this sorting issue.