
http://www.youtube.com/watch?v=LIWonR67u4o
[Front-paged. -stabguy]
The main title page says "Executing the Executioner", which is almost the same as Stabguy's video on stylishly killing Majd. This one actually includes the 'execution' kill-move, though.
Swift Death
This relies on exactly the same mechanics as my Pre-exposed Blitz, but it takes very little setup time. I imagine it would be better to start from a position closer to Majd, but you'd have to piss off the guards real quick, or Majd will stay at the podium unless you wait, at which point you've got a bunch of guards taking swings at you. I didn't feel like trying over and over. I watched enough of Malik and Majd's blabbering during the making of the Pre-exposed Blitz.
Time taken is something like 6.5 seconds.
Instant Retribution
...after having been warned. While playing around in the area, I found this neat spot above the stage where you stand atop of the branch. You can't move or do anything really, or you'll fall. The spot is very easy to get to, you just need to find the correct place to wallrun, which is just a bit off from the side.
Base Jump Stunt
I called this a stunt, even though Altaïr doesn't take damage in the video. The description for 'stunt' in the Advanced Techniques Summary states: " The height of the fall should be sufficient to cause injury." And the height is, just not if you roll. Whether or not this can be classified as a stunt, it is a very stylish kill.
To start off, go to flag #14. From there you have to make quite a tricky jump, but you have plenty of time while Majd is busy talking. Once you land in the right spot, you have to punch yourself up a bit and then turn back around. If you look closely, you see this is because the wall isn't vertical, but diagonal at that height. When you get up top, you just wait for Majd to walk out, drop down, et voila.
Note how the assassin was killed. There is no penalty for this (if you wait too long you'll desynchronize, though) and Malik makes no note of it.

http://www.youtube.com/watch?v=893anT8UDjA
[Front-paged by stabguy]
For the setup for Back to the Future on Majd Addin watch the original video.
http://www.youtube.com/watch?v=MKrs0HyY7hg
Stunt
Thanks to the exploit the target walks away to the temple area. This gives a window of opportunity to stunt assassinate him anonymously. Now the ground in the execution area is on a low level, while the path Majd takes slopes upward. To get a sixteen block stunt (the highest amount of damage Altair can take without dying) you need to perform the stunt before the target goes up the stairs. There just so happens to be a beam from which you can lose sixteen blocks of health by jumping off of. You'll need to hurry though. Majd starts walking that way as soon as the scene ends. Luckily he's on the other side of the area, and the crowd might slow him a little. If you're fast enough you might have a few seconds to spare. I had to do this stunt a few times because of mistiming, but in the end it worked out well with a stationary kill animation.
I also included the escape afterward.

http://youtu.be/fJlv36uWC8c
[Front-paged. -stabguy]
A collection of additional assassinations in AC1, made possible by back to the future exploit.
Maria
Start this the same way as the original early assassination of Maria.
http://www.youtube.com/watch?v=EaikxWTUYVI
Reinitialize the memory by going through the city entrance in the south of Jerusalem. The game doesn't recognize Maria as a target anymore. Now there is no memory corridor scene, and Maria stays dead. It's probably possible to get an instant kill from this by taking out her health and talking to the bureau leader, but I didn't have enough time to record more.
Sibrand
Start this the same way as the original early assassination of Sibrand.
http://www.youtube.com/watch?v=3Tww7kpXiA8
Reinitialize the memory by going through the city entrance in the north part of Acre (there's also an entrance in the eastern part, but you desynch before getting there from the game thinking you already started the mission). Sibrand usually goes onto the docks and walks back and forth along them just like the guard patrol. He's unresponsive to you, but still reacts to seeing dead bodies (in the original Back to the Future assassination he can detect you and would run back to the ship to get to the guard tower). Now that the game doesn't recognize him as a target there's no memory corridor scene. You can also take out his health for an instant kill, but it isn't very interesting.

http://www.youtube.com/watch?v=xUX0ywBguqM
[Front-paged by stabguy]
Setup
To start this glitch out of the city and restart the assassination mission. Here's the original video.
http://www.youtube.com/watch?v=MKrs0HyY7hg
By restarting the mission this way you change the mission structure. The game still thinks you have to assassinate Majd even though you haven't started the assassination cutscene yet. However Majd is nowhere to be found. You can still hear his voice, though, and the target sign on the map is fixed where Majd should be on stage. So go to one of the city entrances to reinitialize the memory. Go back to the execution area. Majd Addin is somehow there. The first time I did this he was walking out of the area, but every time I try it now he is glitched under the stage (seriously, what's up with me getting extremely lucky the first time?!). This is because the game can't model objects from far distances away, and they disappear, a technique known as "There is no Spoon" (or "TINS" for short).
Luckily, Majd isn't unresponsive and can fight you. If he does a combo kill he glitches out. Killing him will result in a non-story assassination with no memory corridor scene.
Instant Kill
I wanted to see what would happen if you took out the target's health without assassinating him, and then restarted the mission. And to make it better I took out his health on the bureau entrance. Well, as you can see, the game recognized him as a target and teleported Altair for the kill. I also tried taking out his health in the execution area to see what would happen. The cutscene seems to have started during the kill and ended. All the HUD elements disappeared and didn't reappear until I desynchronized. The invisible memory barriers during the scene were still there, which I had to glitch out of. One thing I also tried was leaving Majd alive and restarting the mission, but he disappeared. Too bad, I wanted to see what would happen if I had managed to clone him.

http://www.youtube.com/watch?v=Apmob4kOYug
[Front-paged by stabguy]
So it turns out Abul Nuquod can be killed before it should be possible, even though you can't get to him without the memory recording.
Setup
For the basic setup watch the original video.
http://www.youtube.com/watch?v=OHvrRuha1K8
You get in the place by countering a guard through the other side of a wall.
Early Death
After glitching inside the palace the memory starts recording before you reach Abul Nuquod. Walk to the front where you can fall off the roof. There's an invisible barrier that prevents you from going back inside (and in this case also a blue memory wall from being exposed). Walk to the nearest city entrance. You will receive a message that the memory will reinitialize if you leave the city. Going further will refresh the memory and allow you to regain high profile actions. So run back to the palace. Guess who is strolling out the side door? Abul, and maybe one of his bodyguards (I've done this only twice, so I don't know the chances). The game doesn't delete them when you reinitialize the memory, probably because they don't appear until the memory starts recording (actually you can see the bodyguards on the balcony from outside the front door, so it's probably based on distance until the memory starts recording). The palace is empty, and there is no target on the map. Even after killing Abul Nuquod you still have to start the mission again.

Note: Aurel found this first and then told me about it, so I didn't really do anything.
You can do this by starting the William assassination at the bureau and then infiltrating the fortress without the scene starting (see this article). At certain points in the fortress, all the soldiers will disappear. You can then setup an 'invisible kill' with air-to-assassinate: you lock onto your target and make sure you jump through one of these spots. Near the back of the group is a great spot.
Altaïr then performs an air-assassination (
) and the memory corridor scene starts. Afterwards, you can just stroll out of the area and get back to the bureau, after which you will have completed the mission.
I opted to get out of the city instead, to see if the back-to-the-future exploit worked. It didn't, but William's army has become substantially smaller, which makes setting up an anonymous kill very easy with a couple of knives.

http://www.youtube.com/watch?v=MKrs0HyY7hg
[Front-paged by stabguy]
What if Majd Addin stopped killing people and just walked away? Well... My latest exploit does just that. I introduce to you Back to the Future exploit!
Setup
After killing Majd Addin go to the main gate of Jerusalem. Get the attention of the guards outside by killing the guards inside. Now the guards outside will try to get to you by climbing the beams. Here's a way to get them to temporarily fight you. Hang on the beam by the gate and when a guard comes he will throw rocks at you. Drop down and for a short while he will attack you before going back to the beams. If you manage to counter an attack you will glitch through the gate! Now fast travel out of there and come back.
Back to the Future Exploit
Upon arriving back in Jerusalem the gate will be open (probably because you are not under city alert). When entering you will be told that leaving the city will reinitialize the memory. Go talk to the bureau leader Malik. You will start the mission again as usual. But what has changed? When you get close you will hear the crowd talking as though the scene had just ended. Then you might hear the first victim talk. When you start the scene Majd will start saying what he last says to the first victim, and a few more things in the scene are out of sync. The scene ends with a long pause and Majd killing the first victim. As a result he falls off the stage and walks away. Because you weren't detected there isn't a distance restriction, but you can't follow him without crossing an invisible line that ends the mission. Now there are a few other ways this could end. If you don't hear the first victim speak before the scene you will hear her during the scene, and afterwards Majd will glitch partway into a wall. You are unable to lock onto him or assassinate with the hidden blade but can hit him with a weapon, which can get his attention but might also move him too far into the wall. Another way this could end is by having the second victim talk before the scene. I found that if you get away from the stage you can make more of the after-scene dialogue happen. The farthest I've gotten in the after-scene dialogue is the second victim talking. Now Majd will take a shortcut out of the place by climbing the building. I decided to end the video with an air to assassinate.
The Exploit Explained
Since you fast traveled after the assassination the area was refreshed. And by coming in through the gate you reinitialized the memory. So you start the assassination again, but the game knows you already did the mission, which results in the after-scene stuff happening before and during the scene. It's like the game thinks you are at two different checkpoints at the same time! For Majd Addin it's a tug of war between the scene and after-scene scripting. So the AI gets confused, and Majd is no longer affected by the scripting after the scene.

http://www.youtube.com/watch?v=s-rL2hsGhRM
---promoted to front page by Ian---
So I went back to find more things in King Richard's Citadel just prior to the scene in memory block four. And I'm glad I did, because I found a much easier way to get in there, as well as some interesting discoveries.
Easy Infiltration

You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialize correctly.
(Second vid below the fold)

http://www.youtube.com/watch?v=OHvrRuha1K8
[Promoted to front page. -stabguy]
Getting inside the merchant king's palace just prior to the cutscene (non-story) is something I have wanted to do in a while. Here's the setup.
Infiltration
You need a vigilante for this. Luckily there's a group of them not far away from the palace. You would first want to kill the guards in between where you want to lead the vigilante. Have a guard fight you to lead the vigilante. This could take a while since most of the time is spent watching the guard struggle with him. But then the guard pushes him away and comes again after you. This is how you lead the vigilante. Make sure the guard doesn't get too far from him or the vigilante gives up and goes back to the others. Lead them to the door of the palace that Abul Nuquod exits out of. You will encounter a group of guards. Kill all but three guards uncluding the one used for the vigilante (this doesn't seem to work if there are more than three guards). Now here's how you get into the palace. If you jump on the platform by the wall of the door the guards will think you are on the other side of the wall and go there. It is a little common in the AC games for guards to think you are somewhere else, especially if it's by a wall. Getting guards to go after you by jumping while crouching is known as the Pathfinding Charm, discovered by IanXO4.
http://www.youtube.com/watch?v=PRdq6ioX8NE
This is where the vigilante comes in. You need to be locked onto a guard so that you are in battle mode and can counter kill your way in the palace. Jump only when the guard and vigilante are struggling so you don't have the guard also trying to go in the palace.
Exploring the Palace
After you get in stay close to the wall to avoid the memory starting. Take the path shown in the video. Notice how the rooftop archers are all gone. Now for Abul Nuquod. Unfortunately you can't get to him without the memory starting. In fact he and his bodyguards don't even appear until the memory starts. So just drop by and say hello to them before starting the scene. So infiltrating the palace doesn't have much use besides saying it's possible.
I've gotten out of the palace by dropping from the roof, gone a far distance away, and come back. From the front door I can see the bodyguards are no longer on the balcony, and possibly also Abul Nuquod, but with no way to get inside it's unclear what has changed.