You have to (re)create your dynamic controls in the Page_Init event - which occurs before the ViewState is loaded.
You can create controls for the first time in Page_Load or most events - just make sure to recreate them in Page_Init when the page gets loaded again.
If you need to keep track of what controls to recreate you have to use non-viewstate storage during Page_Init (ie Session variables) since the viewstate has *not* been loaded.
A nice article explaining the ASP.NET page lifecycle do what:
ASP.NET Application and Page Life Cycle