Execution Plan Regeneration
If we restart the database server these execution plans in memory will be lost: is it possible that the next time the queries run, Sql Server regenerate some execution plans worst than the previous ones?


Absolutely, it all depends on compile-time differences.  For instance, if a plan is compiled and cached with different values than before the plan cached was wiped (for whatever reason:  Service restart, machine restart, free proc cache, etc.), and those different values give a sub-optimal plan for the typical workload then yes that could be a worse plan for the typical workload than the previous ones.

One way around this is to utilize the OPTIMIZE FOR query hint.  As per BOL:


  Instructs the query optimizer to use a particular value for a local variable when the query is compiled and optimized. The value is used only during query optimization, and not during query execution. 


Another method is to use Plan Guides.  Again, as per BOL:


  Plan guides let you optimize the performance of queries when you cannot or do not want to directly change the text of the actual query in SQL Server 2012. Plan guides influence the optimization of queries by attaching query hints or a fixed query plan to them.


Though I will caution you, plan guides can potentially be complicated and I wouldn't personally use them as a first-option to getting the optimal plan(s) you're looking for.  But, nevertheless, they are an option.