1) $appname-$platform (gcc-avr and binutils-avr) The only problem I see is mingw32 (and related packages). While {gcc,binutils}-mingw32 looks fine, I don't know what to do with mingw32-pthreads, mingw32-runtime and mingw32-w32api. 2) $platform-$appname (mingw32 packages) My favorite. Seems to be most readable (IMHO) and can be easily applied to every cross-compiler. 3) cross-$platform-$appname Probably as good as second option, but cross prefix is annoying me.
For number 3, it is nice in that it makes it very clear what the package is. That said, isn't that already covered by the description? I for one never explicitly install a package without first knowing what it is and why I want it, and I have a feeling I'm not in the minority on that one. I'm slightly more of a fan of number 1, since these are variants of the application, but I think its better just to get one naming standard and stick to it than to have something that everybody likes. The difference between 1 and 2 makes it just a matter of which feels nicer; both are easy to search for.