Maybe this information is worth to share, so here is the cause of our problem.
The richfaces strategy for reloading scripts after an AJAX request doesn't work correctly in the above scenario. The URLs for the scripts looks different for page refreshs and AJAX refreshs. This means for the first Ajax refresh after a page load, the allready loaded scripts are reloaded. This breaks the oncomplete script.
We fixed this issue by implementing our own BridgeStragegy.