[SalesForce] Null or Empty value are allowed in Unique and External ID text field

It would be really weird to have lookups silently count as ext. id fields...

Try performing describe calls on all objects in your package that you suspect to clash? I have a custom field marked as "External Id", "Unique Case Insensitive" and I get this:

Schema.DescribeFieldResult f = Account.Account_Number__c.getDescribe();
System.debug(f.isExternalID());  // true
System.debug(f.isUnique());      // true
System.debug(f.isIdLookup());    // true

EDIT: There are 3 unique / ext. id fields per object. Ask support for increase.

BUT

How many formulas do you have on the objects that can be "common" with the other package. And do these formulas utilize in total 10 lookups to different places? (scroll to "Formulas: Number of Unique Relationships Per Object" text)?

I can imagine this being different kind of limit (put in place because too many lookups / formulas make joins in the underlying database extra painful to retrieve data). In that case you might have to consider rewriting some of your lookups into fields updated with triggers (always pain in managed package as I understand).

Upsert depends upon the value of External ID fields being unique. If you choose to not make External ID unique, you cannot leverage this feature. This means that you would need to leverage external logic in order to perform the upsert operations. Either clean up your data, or use external logic. One potential solution could be to write a trigger to eliminate a previous External ID matching the record's value when it is inserted or updated; you'll still need to clean up data that existed before this trigger was implemented. Off the top of my head, your trigger might look like this:

trigger clearOldIds on Contact (after insert, after update) {
    Set<String> newIds = new Set<String>(); // All new ID values
    for(Contact record:Trigger.new)
        newIds.add(record.External_Id__c);
    newIds.remove(null); // Ignore blank values
    Contact[] others = [SELECT Id FROM Contact WHERE External_Id__c IN :newIds AND Id NOT IN :Trigger.new];
    for(Contact record:others) // Clear old IDs
        record.External_ID__c = null;
    update others;
}

This would probably work in most cases, but you'll need to clean up your data at least once for this to operate correctly.

Another solution would be to create a service that your external service could consume. Here's a primitive example that would cover this:

global with sharing class SystemUtils {
    global webservice void upsertLast(Contact[] records) {
        Map<String, Id> uniqueValues = new Map<String, Id>();
        Contact[] newRecords = new Contact[0], oldRecords = new Contact[0];
        for(Contact record:records)
            uniqueValues.put(record.External_ID__c,null);
        for(Contact record:[SELECT Id,External_ID__c FROM Contact WHERE External_Id__c IN :uniqueValues.keySet() ORDER BY SystemModStamp ASC])
            uniqueValues.put(record.External_Id__c, record.Id);
        for(Contact record:records)
            record.Id = uniqueValues.get(record.External_Id__c);
        for(Contact record:records)
            (record.Id==null?newRecords:oldRecords).add(record);
        insert newRecords;
        update oldRecords;
    }
}

I haven't implemented error checking, that'd be the last step, but this sort of code would conceivably work assuming there were no errors.