Hmm, I may be in error, but I believe the crosses I am talking about are supposed to represent those people who don't have me on their contact list (i.e. because they never accepted me or deleted me or whatever). That is indeed what the FAQ
describes. They appear when I enable the option "Show special icon for contacts that do not have you in their list", in the Preferences -> Advanced dialog.
I am talking about the icons seen in this example:

I do see a few people with those crosses by their name. For some of these contacts, it makes sense, since we haven't spoken in years; but for others I know that they have me on their list.
The exact same problem manifests itself (with the same contacts) in the "Reverse List" window, in the Preferences -> Privacy dialog. At the bottom there are two lists: "User's Contacts" and "Reverse List". As I understand it, the "Reverse List" is supposed to indicate those people who have you in their contact list. The FAQ also
explains it as such.
There are at least 2 people who I know for a fact have me on their contact list (I know them personally and they have initiated chats with me), however they do not show up in this Reverse List, and they have the red cross in their name (even while chatting with me).
Unless I am mistaken, the official MS client also has a similar Reverse List (perhaps with another name), where one can see who has you as a contact. I haven't had access to a Windows machine to check whether the reverse list from the MS client matches the reverse list from aMSN, but I should be able to check during the weekend.