Unable to play game which was bought, payed and downloaded

Press the Guide button on the controller and scroll left then choose Active Downloads to ensure the game isn't still downloading.  

If it's not then go to System>Accounts>Download History to restart the download.

If it is still not there you can check your purchase history at https://commerce.microsoft.com to ensure the sale went through and it was purchased on that account.

Thank you for the reply, but I'm sorry to tell you that I already did all those steps.

It might be interesting to know that I live in Luxembourg, a country which is not listed in the countries which support xBox Live.

Could it be that the game is region blocked and therefore would not show itself in my games library.

I also found out that the game file on my harddrive says that it is corrupted or damaged.

I already cleaned the cache on the harddrive and tried downloading the game a few times, but it is still the same.

If Xbox LIVE is not supported in your country how exactly are you getting on Xbox LIVE?  Circumventing regional lockouts is a violation of the Terms of Service agreement.

Live works fine in my country for playing online and downloading game demos and dlc, but it seems that live is not fully supported when it comes to buying things in the store. Luxembourg is not in the list of the countries that can be chosen for credit card transactions.

So there will never be an answer to this issue?

It sounds like it could be a region issue. If you are downloading the game, but the download stops and then the file is corrupt, the game could be region locked. Since you don't live in a supported country the game may not be available for download there. There is no way around region locking.