Exhaustive SQL stored proc validation make insert slow

This issue is called parameter sniffing.

Later versions of SQL Server give you more options in dealing with it such as OPTION (RECOMPILE) or OPTIMIZE FOR hints.

You might try declaring variables in the stored procedure, assigning the parameter values to the variables and using the variables in place of the parameters as it sounds as though most of the time you are getting a reasonably satisfactory plan.

Normally the most catastrophically bad plans are those compiled for parameters with very high selectivity but ran with parameters with low selectivity.

Assuming the plan generated is more robust with this approach and satisfactory for all parameter values then the advantage of this approach over that suggested by JNK is that it does not incur a compilation cost for every call.

The disadvantage is that for some executions run time might be greater than for a plan tailored specifically for those parameter values so it is a trade off of compile time vs execution time.

Using OPTION (LOOP JOIN) isn`t suitable since it costs almost 15% more than MERGE JOIN

The cost percentages displayed in showplan output are always optimizer model estimates, even in a post-execution (actual) plan. These costs likely do not reflect actual runtime performance on your particular hardware. The only way to be sure is to test the alternatives with your workload, measuring whichever metrics are most important to you (elapsed time, CPU usage and so on).

In my experience, the optimizer switches from loops join to merge join for foreign key validation far too early. In all but the largest operations, I have found loops join to be preferable. And by "large" there I mean tens of millions of rows at least, certainly not the thousand or so you indicate in the comments to your question.

In my opinion there must be a way to make the validation phase for the inserted set faster at least for the immutable attribute.

This makes sense in principle, but there is no such logic today within the plan-building logic that foreign key validation uses. The current logic is deliberately very generic and orthogonal to the wider query; specific optimizations complicate testing and increase the likelihood of edge-case bugs.

Is there any common pattern to overpass the situation above using code structures, additional DDL objects, etc?

Not that I am aware of. The deadlock risk with merge join foreign key validation is well known, with the most widely-used workaround being the OPTION (LOOP JOIN) hint. There is no way to avoid shared locks being taken during foreign key validation, because these are required for correctness, even under row-versioning isolation levels.

There is no better general answer (than the loop join hint) if you want to retain the ability for multiple concurrent processes to add rows to the parent and child tables transactionally. But, if you are willing to serialize the data modifications (not reads), using sp_getapplock is a reliable and simple technique.