According to every source I've run across, it's because they simply haven't changed the addresses since the city was incorporated in 1898, before which Manhattan and Brooklyn really were separate cities. Interestingly enough, this also explains why you sometimes send a letter to "Brooklyn, NY," but never to "Queens, NY." When the city was incorporated, Brooklyn was a solidified city entity, but Queens was only a set of villages, much like the towns/villages further out on Long Island still are today (although they are frequently grouped together by their county designation).
I guess old habits die hard. In 1898, "City People" were horrified and depressed by being united with those country Brooklyn dwellers. Over a hundred years later and Manhattanites are still offended by being grouped together with Brooklynites.