It seems, I have managed to find the reason of this strange issue. This can happen if the name of a WP app includes spaces! I noticed that if we create a new project and use the space character in its name, the spaces are replaced with the underscore characters on the phone (for instance, "WP Test App" is deployed under the name "WP_Test_App"). I also found this while searching for a solution of this problem:
App doesn't get updated then debugging - incrmental update not correctly working?
I played a little bit with the names of my project and solution, i.e. removed the spaces in them, and it helped to solve my puzzle.
BTW, as the author of the question under the above link states, this problem never occurred in the WP 7.1 SDK - it is specific only for the WP 8 SDK.