Does there exist a platform where readdir returns . and .. in other than the first two return values?

Yes! Though it took me three months after reading this question to realize it... or possibly something changed in the system setup during those three months. But in any event, I have an example case:

% ls -a
./   ../  10   11   2    4    5    6    8    9
% perl -le 'opendir DIR, "."; print join " ", readdir DIR'
. 2 4 5 6 8 9 .. 10 11
[download]

The files were created in the order 2,4,6,8,10,5,9,11 (you could say this was an artificial test case, I suppose...), but this does not seem to affect the sort order. The result is the same running on 5.004/Irix and 5.005/Linux: the key is seems to be the underlying filesystem, which is SGI XFS (under IRIX 6.5).

As a further (and yet more psychotically artificial) test, we have

% touch ,
% ls -a
,    ./   ../  10   11   2    4    5    6    8    9
% perl -le 'opendir DIR, "."; print join " ", readdir DIR'
, . 2 4 5 6 8 9 .. 10 11
[download]

I haven't done an exhaustive investigation of exactly what XFS does for all cases, but it seems fairly clear that one-character filenames will, in general, break the common assumptions of readdir on that filesystem.