If I know a startup has a valuation of $X million pre-money, received $Y million from VC and is now evaluated at $X+Y millions, how much percentage of the company were given to the VC?
You can't quite calculate that from the numbers you have. If the company was worth X, then investors added Y in cash, then just after the transaction completes the company is worth X+Y, as you write. That's because one dollar in cash is included in the valuation as .. one dollar.
This doesn't give you absolute certainty about the ownership percentages; these were determined by (confidential) negotiation. Depending on the relative strength and the intentions of the negotiating parties, the investors could take home a larger or smaller ownership share for their investment.
Having said that, the investors will generally take (Y/(X+Y))*100 percent ownership. Here is an article that explains the calculation (note that ESOP means "Employee Stock Options Pool"). Also see this previous question.
I guess that investors in later stages would always follow the formula linked above -- if people deviate from it, then it's probably in the very early stages of a company, where valuations are quite uncertain anyways.
And if, say, 20% have gone to VC, 20% more are in the employee stock pool, does that mean the 3 others founds have 20% each? Or are the shares "on hold" usually for some reason?
The 3 founders could have 20 percent each. Or they could have a different split; if they began with different ownership percentages (any split is possible). They could also have "vesting", a sort of earn-your-shares-over-time, which could mean that they don't own all of their allotted shares yet.