Quagnoth uses an item out of his inventory at 23m 45s into the VOD. You wouldn't have this item on a NG run. So, this run should be invalid. Correct?

Link with timestamp to the VOD:

The item he used is the fireteam medallion, the community (overwhelmingly) decided that you were allowed to use it in NG runs as it makes the run faster and reduces the luck needed for the run

How do I run NG if I don't have it?

after you have a character finish the campaign you are given one, you get one everytime you have a character finish the campaign. You can also buy them from eververse for 50 bright dust which is pretty easy to get

So, I can't complete a New Game run without beating the game? Sounds like NG+ to me... :-/

There's nothing stopping you from doing a ng run without the fireteam medallion. The fm just speeds up getting the loot

It was voted to be allowed because they're extremely easy to obtain and without it (even with it) the run is incredibly luck based and long. So for the sake of reducing such luck and the fact that they are really cheap it was voted in. Like Lonne said, there is nothing stopping you from running without it.

ok cool thats what i thought thanks for the clarification FleshCrunch

Also my run (second place) is without a fireteam medallion so its not impossible to get that time without the medallion.