Basically, updating the statistics was a pretty good idea.

The execution time of a certain query could be reduced from more than 10 mins down to 1 minute.

For some reason, I don't know and still try to figure out, our good old server with just 1 processor 8 GB RAM performed better than our SQL 2008R2 with 16 GB RAM and 4 processors. Maybe, is results from the fact that it is running on a virtual machine (Hyper V).

Another reason maybe that the SQL Server is running with 80% compatibility.

I will be back soon and keep you updated.

Thank you all for your very informative tips and hints.

When the migration finally succeeds, I am going drinking a beer or a soda. 😉