Au vue des différentes contraintes que tu m'as exposé, et en particulier un ratio de 100 allocations pour 1 libération, n'importe quelle méthode fera l'affaire.
Même une simple pile qui ne libère jamais devrait pouvoir faire l'affaire. Ca te coutera 1% de ta mémoire. La taille d'un bitmap qui pointe vers les zones libres.