Porque é que a maioria dos nomes de pacotes Android começa com com?

A razão é para evitar a escolha de nomes entre aplicativos.

A convenção é para usar o nome de domínio reverso porque a maioria (todos?) dos editores possuem um nome de domínio único que quando prefixado ao nome do aplicativo, gera um nome único para o aplicativo.

A razão para tê-lo em ordem inversa tem a ver com o layout na mídia de armazenamento. Se você considerar cada período ('.') no nome da aplicação como um separador de caminhos, todas as aplicações de uma editora ficariam juntas na hierarquia de caminhos.

Então, por exemplo, pacotes da Adobe seriam da forma:
com.adobe.reader (Adobe Reader)
com.adobe.photoshop (Adobe Photoshop)
com.adobe.photoshop (Adobe Photoshop)
com.adobe.ideas (Adobe Ideas)
br>[Note que isto é apenas uma ilustração e estes podem não ser os nomes exatos dos pacotes]

Estes poderiam ser mapeados internamente (respectivamente) para:
com/adobe/reader
com/adobe/photoshop
com/adobe/ideas

p> O conceito vem das Convenções de Nomenclatura de Pacotes em Java, mais sobre o qual pode ser lido aqui: http://en.wikipedia.org/wiki/Java_package#Package_naming_conventions