So recently we had some issues that came up around the "My
SharePoint Links" option that exists on default master pages under the
menu option "My Links". Our issue was that a few sites never showed up
on that list for some people during testing. This spawned a number of
questions about this process, which I decided to share, as I couldn't
find much on the Internet currently about this. This is the
information I've found, seen, and some is my best guess, based on the
behavior of the system.
When My SharePoint Sites shows up
My SharePoint Links only shows up when you have multiple Site Collections. If you are working with one Site Collection, the list item for these links will not appear. After adding another collection, there is a waiting/polling period before it appears. This seems to be 5-30 minutes usually. My best guess is that this is linked to an sptimer job, although I haven't found information on that yet. This appears to be the same job that "converts" a new site to standard security objects (see below).
Which Sites show up on the My SharePoint Sites list
So which sites belong on that list? Any site for which the current logged in user is in the configured "Members" group. Owners, Admins, and Visitors make no difference for this list, only Members. This is the same list that is populated on MySites in the profile section labeled "Memberships". You can manage these at http://<mysite_root_url>/_layouts/MyMemberships.aspx...
How security is setup originally
As far as I've been able to tell, any given site, when created, contains a custom list for security that is not linked to actual security objects. It does seem to link to AD security principles (the "Account" field), but the rest on the information is just standard editable fields (see screen shot below).
You can get to this first screen by adding _layouts/people.aspx to your
site address (It's the people section of People and Groups), then
select settings, list settings.

This second screen is accessed by just clicking on the user's name or image in a security group or the All Users screen.
After a 5 to 30 minutes time period (this seems to be about the same time period - and perhaps the same sptimer job? - as updates to your MySite "About Me" section, which appears in the user info screen), the security information is updated, and looks like the screen shots below.
Notice that there are only two columns listed (above), and all the fields in the User Information (below) are now read-only.

At the time when this change happens, the site will now appear on the My SharePoint Sites list. My belief is that this conversion process changes the security table to a series of objects that are now readable by SharePoint's core system as security, rather than a list. The My SharePoint Links object calls a security lookup that cannot read from those unconverted sites, only from converted ones.
When things break...
So what exactly was the problem we were seeing then? Based on the above information, I found that the few sites we had that never populated on the My SharePoint Links list all still had that "new site" security list that had not yet been converted. The sites had been created days ago, in a few cases over a month ago, but the sites never changed.
This led me to alter my belief about this possible sptimer job. The behavior makes me believe that there is a "convert flag" somewhere in the site information that tells SharePoint if it is a new site, or a converted site. This (possibly fictional) sptimer job only converts sites where the flag has not yet been set, and it sets this flag after the conversion.
How to fix it when "things break"...
Unfortunately, my call to MS Premiere ended up being a bit more of an educational session for them, and I still do not have a reasonable answer to this issue, although the issue is still open and they are researching this behavior now. I did find that I could easily use my MOSS backup solution, AvePoint's DocAve, to backup content and restore it to a new site that had been converted, but this still leaves the question of how to fix a site without a 3rd party tool and a bunch of delete/recreate operations. I'm still waiting for that answer, but now I think I understand how this part of SharePoint functions a bit better. I'll post the answer (if there is one) whenever I get it...