Is this guaranteed to be correct?

[superbonzo]

Also, I'm not 100% sure the id's will be guaranteed identical for types originating from separately compiled units.

a conforming compiler should guarantee that ( as long as some requirements are fullfilled, see post#3 )

What I my class is designed to do is this.

as suggested in post #9, you can avoid the NextUniqueId() function calls, at the cost of either a (possibly small) runtime or space penalty. For example, something like ( c++03 compatible, off the top of my head solution, not tested ! ) :

template< typename T1, typename T2 >
struct SameType { static const bool value = false; };

template< typename T >
struct SameType<T,T> { static const bool value = true; };

struct NoType {};

template< typename T, typename T1 = NoType, typename T2 = NoType, typename T3 = NoType > // ... up to some Tmax
struct TypeMap
{
	// return the position, or -1 if not found

	static const unsigned value = SameType<T1,NoType>::value ? -1 : ( SameType<T,T1>::value ? 0 : ( 1 + TypeMap<T,/*T1,*/T2,T3>::value ) );
};

template< typename T1 = NoType, typename T2 = NoType, typename T3 = NoType > // ... up to Tmax
struct Any
{
	unsigned id;
	// ...

	template < typename U1, typename U2, typename U3 >
	bool IsSameType( Any<U1,U2,U3> const& other )
	{
		// the compiler should be nice enough to optimize obvious branches and apply lookup/binary search whenever appropriate

		switch( other.id )
		{
		case 0: return id == TypeMap<U1,T1,T2,T3>::value;
		case 1: return id == TypeMap<U2,T1,T2,T3>::value;
		case 2: return id == TypeMap<U3,T1,T2,T3>::value;
		default:return false;
		}
	}
};

or

template< typename A1, typename A2 >
struct AnyCompare { };

template< typename T1, typename T2, typename T3, typename U1, typename U2, typename U3 >
struct AnyCompare< Any<T1,T2,T3>, Any<U1,U2,U3> >
{
	static const unsigned Map[] =
		{
			TypeMap<U1,T1,T2,T3>::value,
			TypeMap<U2,T1,T2,T3>::value,
			TypeMap<U3,T1,T2,T3>::value
		};
};

// ... possibly more specializations to compress size ( otherwise, for each Any instantiation you'd end up with a Tmax-sized static lookup table )

// ...

	template < typename U1, typename U2, typename U3 >
	bool IsSameType( Any<U1,U2,U3> const& other )
	{
		return id == AnyCompare< Any<T1,T2,T3>, Any<U1,U2,U3> >::Map[ other.id ];
	}
};

the first code has no space overhead and a runtime overhead depending on how much the compiler optimzes the switch, whereas the second code has no runtime overhead but a per-instantiation space overhead varying from 1 to Tmax times your current solution, depending on the AnyCompare specialization.

Note that you can use the (boost)preprocessor(library) to generate the Tmax dependent boilerplate code ...