Short answer:
If you look hard enough, many games have been called "Game of the Year" by some people and sometimes these people come together and agree on this opinion and declare these games their collective Game of the Year. Regardless of how important these people are or aren't, that game can rightfully say it has been called Game of the Year in some way or another.
Longer explanation:
Before Googling Game of the Year for the first time, I assumed that GOTY simply meant "Game + all of the DLC," but it looks like MOST of these games actually won Game of the Year awards from some institution or another.
According to the list of Game of the Year awards on Wikipedia, there are actually a number of GOTY award-givers for a given year (52 to be exact).
Thanks to some steam searching by jojo, it looks like Deus Ex Machina and Rising Storm are not on this list, yet do have GOTY editions. Thus, it may be just a marketing gimmick. However, I was surprised by a number of games that I did not expect to see on the above list, so GOTY may have more credibility than I'd thought.
After doing some careful Googling, I found that all but one of the exceptions to the GOTY recipient idea mentioned in the updated question as well as the other answers actually did receive Game of the Year awards from at least one place, though some are relatively obscure.
Question:
Deus Ex Machina Game of the Year: CTA Game of the Year award (1985)
Rising Storm: PC Gamer Multiplayer Game of the Year (2013)
Project Cars: Techly's Game of the Year Award for Best Graphics (2015)
Badland: App Store iPad Game of the Year (2014)
Two Worlds II: Bestes Rollenspiel & Bestes Spiel (translated: Best Role-Playing Game and Best Game) (2011)
L.A. Noire: BAFTA Game of the Year for Best Original Score (2012)
Kohan: Immortal Sovereigns: Academy of Interactive Arts and Sciences Best Computer Strategy Game of the Year & PC Gamer, Computer Gaming World, and Computer Games Magazine Strategy Game of the Year (2001)
Call of Duty 4: Modern Warfare:
- Game Critics Awards: Best Action Game
- GameSpot: Best Graphics, Best Shooter, Best Xbox 360 Game, Best PS3 Game
- GameTrailers: Best Graphics, Best PS3 Game
- GamePro: Best Overall Game of the Year
- IGN: Best Xbox 360 Game, Best Shooter of 2007
- GameSpy: Best PS3 Game, Best Xbox 360 Game, Best PC Game, Game of the Year
- X-Play: Best Shooter, Best Sound Design
- Spike Video Game Awards: Best Shooter, Best Military Game
- Academy of Interactive Arts and Sciences: Action Game of the Year, Console Game of the Year, Overall Game of the Year
- Golden Joystick Awards: Game of the Year
In Memoriam/Missing Since January: Computer Gaming World's Adventure Game of the Year (2004)
Plants Vs. Zombies: Golden Joystick Awards for Download Game of the Year & Strategy Game of the Year (2010)
Worms: Reloaded: This one is a bit difficult to prove, as the franchise has been awarded multiple "Best Game"-type awards and many are foreign, but due to the fact that there is only one Game of the Year Edition of any game in the Worms franchise, it is very likely that Worms: Reloaded was the recipient of at least one of these Game of the Year awards.
The one and only game listed in the question and answer that I cannot find a definitive award for is Men of War: Assault Squad.
Due to this being the sole exception that I have found, releasing a GOTY version of a game should not be seen as a simple marketing gimmick. That is not to say that the intent of releasing such a version is not to generate more revenue, however, there is definite credibility behind releasing a Game of the Year edition.
While finding awards for the games listed in the question and other answers, I have come to the realization that due to the rising popularity and diversity of games, a singular "Game of the Year" no longer works. One person's Game of the Year may not be another person's Game of the Year. In fact, it most likely won't be.