I reported this 6 months ago (https://dev.twitter.com/discussions/12833) and sadly it has received no attention by Twitter. I see this inconsistencies for about 60% of my users, so I had to work around it by making an extra request to friendships/exists to verify the results. Surprisingly (and fortunately for me) that endpoint does return consistent and accurate results.
I really wish Twitter acknowledged this problem, it’s really sad to see how one of the most important features, the friendship graph, is completely broken.