After suffering "internal injuries" and looking for two days in-game for a replacement heart, it dawns on me why this is always so hard: There is only one type of cyber heart in the game, and since the game draws fairly randomly when stocking shops, this makes finding a replacement heart very unlikely, especially since almost every other cyber body part comes in multiple flavors.
Thus, I created two new cybernetic hearts. Enjoy!
StatCyberware
Name <Gold Heart>
desc <(HEART) This artificial heart pumps drugs throughout the body that promote self-worth.>
Category <CYBERWARE MEDICINE>
Factions <GENERAL>
CyberSlot <HEART>
Ego 2
Body -1
Mass 2
legality -15
StatCyberware
Name <Juiced Heart>
desc <(HEART) Purer oxygen mixed with stimulants makes this person feel contantly refreshed.>
Category <CYBERWARE>
Factions <GENERAL>
CyberSlot <HEART>
Reflexes 2
Speed 2
Charm -1
Mass 2
legality -5
EDIT: Actually, adding two new cyberhearts did nothing. The problem was that most doctors/cyberdocs only carry cyberware that will grant a stat increase of one, and since the default cyber heart grants a bonus of 2 body, the cyber heart default never would show up. However, by giving my Golden Heart a negation of one body (and making it eligible for "MEDICINE"), it will now appear regularily.