Although not mentioned in the documentation, the method marked with the AssemblyCleanupAttribute must exist in a type marked with the TestClassAttribute (although no tests need to be present), for the Test Tools engine to run it.
For example:
[TestClass]
public class AssemblyInit
{
[AssemblyCleanup]
public static void AssemblyCleanup()
{
}
}