Brother Salam, your question is valid and shows you are careful to understand and comprehend the different aspects of your religion well enough in order to enhance your faith. And that is valid and to be supported. Some people face what they don't understand and try to change it in their minds to something acceptable, or look for a single sheikh to give them an alternate ruling that would go with their desires, which is an unfortunate weakness and may God make us all stronger. You are not like that though and I am glad you asked rather than do like many modern muslims who simply choose to take the opinion of a very small minority, that there should be no punishment for apostasy.
First, before the explanation, here is the nass el-hokm (statement of ruling), as per an authentic hadith from the prophet who said: "The blood of a muslim is not halal except in three: Apostacy after Islam, murder of another muslim, and adultery after marriage." also, there is another in Sahih Al-Bukhary narrated by Ibn Abbas: "“Whoever changes his religion (out of Islam), put him to death.” This is a direct ruling with no ambiguity. Additionally, the solid documented history of the prophet and the four Khalifas showed many situations were this punishment was applied on apostates, and explanation of its rulings and conditions was comprehensive. The prophet -pbuh- did it, and on women as well, Abu Bakr waged a whole war on apostates, Umar Ibn Al-Khattab applied it and said that the repentence period is three days, Uthman Ibn Affan upheld it, Ali upheld it and was of the opinion that repentence is one month (and there was an incident where the execution was done by burning the apostates and Ibn Abbas sent to him that the prophet -pbuh- has forbidden using such a method ever, that it is God's sole method of punishment.)
Now, the reasoning behind it is as such: God says in his glorious book: [SIZE=+2]
"وَمَا خَلَقْتُ الْجِنَّ وَالْإِنسَ إِلَّا لِيَعْبُدُونِ" [/SIZE]{I have only created Jinns and men, that they may worship and serve Me} [51:56] and based on this, our very existence is to worship and serve God, Allah -SAW-. This life, this world is nothing but a testing ground to see who worships God the most, who worships less, and who joins Satan and his league and disbelieves in God and deals with his religion with arrogance and pride.
If a person did not hear of God's message, and when he does, he doesn't necessarily believe it at first, That is ok, they have that right. There is no compulsion in religion [SIZE=+2]
"لاَ إِكْرَاهَ فِي الدِّينِ"[/SIZE]. That is because anyway you CANNOT literally force someone to BELIEVE something. You can force or threaten someone into declaring that God is there, but no amount of force or threatening can make people believe. Otherwise, if there is no belief, and a person was forced to do prayer or forced to not eat until sunset, then how can there be a reward and punishment? So people are left to make their own choices, in their own time. Some will die dis-believers, and God will punish them. Some will revert to God's religion and be good muslims, so they will reap the rewards. Some will not hear the message, and those God will judge them with his wisdom and justice that overshadows our knowledge and judgement. They have a chance to become muslim maybe until the last breath on their death beds, and that is their choice.
If a person enters Islam and then leaves, that is a different matter. Because then his choice is over and it has been made. As per Umar ibn El-Khattab who says this is the way the prophet -pbuh- dictated, an apostate is locked up for three days being given basic sustenance. A person of knowledge then speaks with him everyday, for the person might have doubt, might have been misinformed, or might be insane temporarily or terminally. Those three days gives the apostate the chance to review himself, and revise his decision, and contemplate, and allows the person of knowledge to answer his question and to assess if he is mentally sound or not. If he is sound of mind and has no interest whatsoever in Islam, then his purpose in life as per the verse {I have only created Jinns and men, that they may worship and serve Me} is over. A non-believer might any day decide to join, but this one, and after being given the chance to repent for three days or one month (Ali prefers a month because he says he understood from the prophet that ample time is the key. Ali Ibn Abi Taleb of course was jurisprudence and Fiqh wise better than Umar) still insist that they won't be muslims, which means that they will NEVER be.
On top of that, there is no chance that a person who apostates from Islam will ever be truthful towards it. They will fight Islam verbally or physically and hold people against it, and try to misguide them by their own stories. So it becomes a combined punishment, of removal of purpose first and of treason second.
As you can see, the basic wisdom of the punishment of apostasy is applicable to both a person who joins Islam, as well as that who was born into it. The one who is born into it and then leaves as an adult despite being exposed to it will still be a traitor (you don't have to have acquired an american nationality to be considered a traitor if you're fighting against them, do you?) as well as irreversibly mushrek and therefore has no more purpose.
There are of course conditions and rules to follow when applying the punishment. Reasons not to apply the punishment other than repentence or the person being found not of sound mind: ignorance, misunderstanding, being forced, and making mistakes.
As for Ibn Taymeyya, he actually described two types of apostasy, ordinary and extreme, for which BOTH deserve the death penalty. However he said the extreme apostacy need no repentence or waiting time. An example of an extreme apostate is like Al-Hallaj in Iraq, who claimed divinity and belief in re-incarnation. He claimed to be God, and was put to death without asking him to repent. Ibn Taymeyya said that al-muhareb or fighters against Islam can be verbal as well as physical, and that verbal fighting is worse than physical, and that all apostates if they do not repent must be put to death.
All these can be found in his books. So the stories that he did not approve of this are wrong.
The punishment for apostasy was actually set from the days of Moses, and it still stands in the modern day jewish scripture:
Deuteronomy
13:6 If thy brother, the son of thy mother, or thy son, or thy daughter, or the wife of thy bosom, or thy friend, which is as thine own soul, entice thee secretly, saying, Let us go and serve other gods, which thou hast not known, thou, nor thy fathers;
13:7 Namely, of the gods of the people which are round about you, nigh unto thee, or far off from thee, from the one end of the earth even unto the other end of the earth;
13:8 Thou shalt not consent unto him, nor hearken unto him; neither shall thine eye pity him, neither shalt thou spare, neither shalt thou conceal him:
13:9 But thou shalt surely kill him; thine hand shall be first upon him to put him to death, and afterwards the hand of all the people.
13:10 And thou shalt stone him with stones, that he die; because he hath sought to thrust thee away from the LORD thy God, which brought thee out of the land of Egypt, from the house of bondage.
13:11 And all Israel shall hear, and fear, and shall do no more any such wickedness as this is among you.
13:12 If thou shalt hear say in one of thy cities, which the LORD thy God hath given thee to dwell there, saying,
13:13 Certain men, the children of Belial, are gone out from among you, and have withdrawn the inhabitants of their city, saying, Let us go and serve other gods, which ye have not known;
13:14 Then shalt thou enquire, and make search, and ask diligently; and, behold, if it be truth, and the thing certain, that such abomination is wrought among you;
13:15 Thou shalt surely smite the inhabitants of that city with the edge of the sword, destroying it utterly, and all that is therein, and the cattle thereof, with the edge of the sword.
13:16 And thou shalt gather all the spoil of it into the midst of the street thereof, and shalt burn with fire the city, and all the spoil thereof every whit, for the LORD thy God: and it shall be an heap for ever; it shall not be built again.
13:17 And there shall cleave nought of the cursed thing to thine hand: that the LORD may turn from the fierceness of his anger, and shew thee mercy, and have compassion upon thee, and multiply thee, as he hath sworn unto thy fathers;
13:18 When thou shalt hearken to the voice of the LORD thy God, to keep all his commandments which I command thee this day, to do that which is right in the eyes of the LORD thy God.
And there is this incident:
Exodus
32:26 Then Moses stood in the gate of the camp, and said, Who is on the LORD's side? let him come unto me. And all the sons of Levi gathered themselves together unto him.
32:27 And he said unto them, Thus saith the LORD God of Israel, Put every man his sword by his side, and go in and out from gate to gate throughout the camp, and slay every man his brother, and every man his companion, and every man his neighbour.
32:28 And the children of Levi did according to the word of Moses: and there fell of the people that day about three thousand men.
32:29 For Moses had said, Consecrate yourselves today to the LORD, even every man upon his son, and upon his brother; that he may bestow upon you a blessing this day.
So in conclusion, I hope that I provided you with a fullfiling explanation regarding the death penalty for apostacy, and that there is no difference between embracing Islam and being born muslim in apostacy. Most importantly I hope your view is also corrected regarding Ibn Taymeyya.
And God always knows best
An apostate is held by the authorized magistrate or judge and is checked on his sanity and discussed with to give a chance to repent as was ordered in Islam. Afterwards they are put to death by a trained executioner without mutilation, keep your samurai sword holstered my friend. 
mg: 
