Peter, thank you for taking care of this. I will voice my opinion.
I checked the other instance of VS on another computer which "Build out of date projects on run" works. It's version number is: 8.0.50727.42. This is developer version of VS from MSDN DVD. The other one with the problem is a standard version. I doubt this edition difference explains the problem because as I said the standard version used to work.
I noticed that though I chose "Prompt to build", it does not prompt, instead it just builds. It works for C# project. It seems VS's behaviour regarding this is quite irregular and inconsistent.