What sort of flavours distinguish ultra-high IBU beers from other high IBU beers? When I've drunk high-IBU beers such as Mikkeller's Hop Burn High (labelled as 300 IBU) I've been able to taste and smell the hops, but I'd be hard pressed to say that it was e.g. 6 times as bitter as a 50 IBU beer.

So I was wondering if there is something about the beer that I'm missing that would indicate that it was a 300 IBU beer?  Or is this more of a marketing thing when breweries label beers with such high numbers?
The brewery really needs to indicate how they get the 300 IBU measurement. Most just work it out from the hops they add using hop bitterness calculators, rather than it being an actual measurement of the bittering compounds in the beer. For highly hopped beers, the calculated IBUs can be far off compared to reality - above around 100 IBUs it becomes more and more difficult to increase the IBUs of the beer.

The isomerized alpha acids that give the bitterness are only marginally soluble in wort (they are hydrophobic), and their solubility decreases as more is dissolved: solubility decreases with lower pH and dissolving the iso-acids lowers the pH, so solubility is self-limiting. 

Thus, labels with over 100 IBUs should not be considered accurate, unless the brewer has specifically measured the IBUs in the beer, rather than guessed them from the hop regime.