Thanks for taking what time you have, Goran, to flesh this out on the
list!  A few more comments:

1. Immutable names does not stop renaminging in practice.  You can still
make a new package with a different name but the same contents.  The new
package can have an alias for the old package, so that existing
dependencies are not broken.  After some grace period, you can remove
the old name as an alias if you want.  This is not a pretty process by
any means, but it works okay assuming people do not change their package
names all the time.  I would expect it is likely for people to change it
once within the first month or two of release, and then maybe once every
few years.  

2. Sometimes people *want* name conflicts.  One reason to have a local
repository is to override packages from the main repository with
something site specific.  So it's nice to support this no matter the
scheme.

3. If people have accidentally named their package the same as an
existing one, do we really want to make this work by using UUID's?  It
should probably give a warning, at least, shouldn't it?  Allowing
different packages with the same name doesn't seem like a useful
feature.

4. Automatic dependencies would be wonderful, but it is impossible in
general.  Maybe you have thought of a scheme that is close enough to
accurate that no one cares?  The Debian people take on the order of a
full year in order to prepare *one* configuration of packages that is
"known" to work together.  Outside of these painful "stable" releases,
they rely on a bit of auto-depedency plus a bit of programmer
annotation.  Surely there are mistakes, but it works out okay. 
Programmers seem to have a decent idea about what their code really does
require.  At any rate, the mistakes they make in the dependency
annotations are dwarfed beside the number of mistakes they make in the
actual contents of the packages.  :)


Lex