Here is what I did for a very similar NPC villain; an Orc Binder with the Unholy Scion template.
Dragon Magazine #354 has an article on "Ancient PCs" and includes a new condition: Endless.
This is pretty much what you are looking for: the character does not age or die of natural causes, they just continue on and on. They can still be killed, suffer poison and disease, spells, etc. but their "clock never winds down" so to speak.
The article also includes a 9th lvl Sorcerer/Wizard spell called "Kissed by the Ages" which grants a creature this Endless quality. The spell is connected to an item that the creature must wear in place of a magic item slot and if it is ever removed they start to age again normally (they also take a -1 penalty to their saves, and a -2 against death effects).
The item can be destroyed but it takes special "artifact killing" rules to do so and the character always knows the location of the object (as long as they are on the same plane).
For this, the spell requires the item to be a magic item of at least 4,000gp and it costs 5,000 XP.
So, for my BBEG (who didn't have access to the spell, the money or the XP) I used the sacrifice rules in the Book of Vile Darkness. He made religion checks to sacrifice victims and in return got access to the Dark Craft points described in that book.. as well as some DM fiat on my part.
Obviously, you don't have to do it the same way I did, and it wouldn't be hard to substitute "sacrifice" for "magic ritual" or make up your own special recipe to grant someone the Endless quality.
Hope this helps
J from Three Haligonians