There is a way to use GUIDs for the class type part of the external id as well.  I posted a replacement external id generator that I have been using.  I have updated the BkpExternalIdServiceImpl since the post back in Jan 2009.  Just in case someone is interested in the latest version, here is the source.

using System;
using System.Collections.Generic;
using System.Text;
using Eco.Services.Impl;
using Eco.Framework;
using Eco.Cache;
using Eco.UmlRt;
using Eco.ObjectRepresentation;
using Eco.Services;
using Eco.DataRepresentation;
using Eco.Handles;

namespace Vco.EcoUtils
{
    /// <summary>
    /// Replacement class for the ExternalIdService used by an EcoSpace. 
    /// This class will use a 22 character base64 string for the class id
    /// part of the external id.  Here is an example of an ExternalId:
    /// qFMNqVavU-iVw1cY2lp_9A!1234
    /// The normal base64 encoding '+/' characters are replaced with
    /// '-_' characters to make the external id url friendly.
    /// </summary>
    public class BkpExternalIdServiceImpl: ExternalIdServiceBase
    {
        private static object lockObject = new Object();
       
        private class EcoSpaceLookupTable
        {
            public readonly Dictionary<string, int> classIdIndexes = new Dictionary<string, int>();
            public readonly Dictionary<IClass, string> classIds = new Dictionary<IClass, string>();
        }

        private static Dictionary<IEcoTypeSystem, EcoSpaceLookupTable> ecoSpaceLookupTables = new Dictionary<IEcoTypeSystem, EcoSpaceLookupTable>();
       
        public static void RegisterTypeSystem(IEcoTypeSystem typeSystem)
        {
            lock ( lockObject ) {
                EcoSpaceLookupTable classIdLookupTable = new EcoSpaceLookupTable();
                foreach ( IClass c in typeSystem.AllClasses ) {
                    if ( !string.IsNullOrEmpty(c.Id) ) {
                        string classId = CompressGuidString(c.Id);
                        classIdLookupTable.classIds.Add(c, classId);
                        classIdLookupTable.classIdIndexes[classId] = c.InternalIndex;
                    }
                }
                ecoSpaceLookupTables.Add(typeSystem, classIdLookupTable);
            }
        }       

        private readonly Dictionary<string, int> classIdIndexes;
        private readonly Dictionary<IClass, string> classIds;

        public BkpExternalIdServiceImpl(IEcoTypeSystem typeSystem): base(typeSystem)
        {
            EcoSpaceLookupTable ecoSpaceLookupTable;
            lock ( lockObject ) {
                if ( !ecoSpaceLookupTables.TryGetValue(typeSystem, out ecoSpaceLookupTable) ) {
                    throw new InvalidOperationException("BkpExternalIdServiceImpl.RegisterTypeSystem was not called for TypeSystem: " + typeSystem.GetType().Name);
                }
            }
            classIdIndexes = ecoSpaceLookupTable.classIdIndexes;
            classIds = ecoSpaceLookupTable.classIds;
        }

        protected override string GetExternalClassId(IObject obj, Locator loc, ObjectId id)
        {
            string externalClassId;
            if ( !classIds.TryGetValue(obj.UmlClass, out externalClassId) ) {
                throw new InvalidOperationException(HandlesStringRes.sClassHasNoModelId(obj.UmlClass.Name));
            }
            return externalClassId;
        }

        protected override int GetTopSortedIndex(string externalClassId)
        {
            int index;
            if ( !classIdIndexes.TryGetValue(externalClassId, out index) ) {
                throw new ArgumentException(HandlesStringRes.sInvalidClassId(externalClassId));
            }
            return index;
        }
       
        /// <summary>
        /// Compresses a Guid to a 22 character base64 string.  If there is a problem making a Guid, it will revert to
        /// removing '-', '{', and '}' from the string.
        /// </summary>
        /// <param name="guidString">A Guid string in a standard format that new Guid(guidString) would take.</string></param>
        /// <returns>22 character compressed Guid</returns>
        public static string CompressGuidString(string guidString)
        {
            try {
                Guid guid = new Guid(guidString);
                return Convert.ToBase64String(guid.ToByteArray()).Substring(0, 22).Replace('+','-').Replace('/','_');
            } catch {
                StringBuilder sb = new StringBuilder(32);
                int length = guidString.Length;
                for ( int i = 0; i < length; i++ ) {
                    char ch = guidString[i];
                    if ( (ch != '-') && (ch != '{') && (ch != '}') ) {
                        sb.Append(guidString[i]);
                    }
                }
                return sb.ToString();
            }
        }

        /// <summary>
        /// Gets a list of all the external class id's.  Primary use is for debugging.
        /// </summary>
        /// <returns>A list of external class id's to use as a reference</returns>
        public string GetClassIdList()
        {
            StringBuilder sb = new StringBuilder();
            sb.AppendLine("External Class Id's:");
            foreach ( IClass c in TypeSystem.AllClasses ) {
                if ( !string.IsNullOrEmpty(c.Id) ) {
                    sb.Append(c.Name.PadRight(40));
                    sb.AppendLine(CompressGuidString(c.Id));
                }
            }
            return sb.ToString();
        }
       

        /// <summary>
        /// Returns the ExternalClassId for an ECO class.  Primarily for use in the debugger to determine external ids on the fly.
        /// </summary>
        /// <param name="className">The class name to get the ExternalClassId from</param>
        /// <returns>The ExternalClassId</returns>
        public string GetClassId(string className)
        {
            IClass iClass = TypeSystem.AllClasses.GetItemByName(className);
            return GetClassId(iClass);
        }
   
        /// <summary>
        /// Returns the ExternalClassId for an ECO class.
        /// </summary>
        /// <param name="iClass">IClass to get the ExternalClassId from</param>
        /// <returns>The ExternalClassId</returns>
        public static string GetClassId(IClass iClass)
        {
            if ( iClass != null ) {
                return CompressGuidString(iClass.Id);
            }
            return "";
        }
       
    }

}