InternetGetConnectedState seems to be a somewhat petulant beast. Some research in the Microsoft knowledge base and the vast rest of the net, while not divulging the excact method used by the function to determine connection, implied that the results could be vastly different depending on the version of Internet Explorer on your system. I found
this entry, which might be of some relevance. You might want to check the default gateway as suggested in the knowledge base article above.