A naive solution could be to just display the first letter of whatever the user has named the given link. Not as helpful as a favicon, but it will prevent the page from looking broken if a bunch of favicons don't exist.
Lots of options: Opera on android generates a favicon if the domain is less than 6 letters just from the letters. Use of colors (hashed from the name I guess) also goes a long way.
No way to fix ugly favicons though. Name of of domain can still be used as well.