It's sometimes said that Henry VII imported the use of 'Your Majesty' into England. Reluctant as I am to acquit Henry VII of anything, I must acquit him of this. Nigel Saul has demonstrated (Richard II pp 340-341) that Richard II was in fact the guilty party.
You will note that in the last post Bolingbroke addressed Richard merely as 'my lord'. I doubt he was being disrespectful, it's just that forms of address at this period had not been codified. So alternate usage was permissible.