Actually this is expected. I checked the site and you are using the recommended practices for the shortcodes its just that you have so many of them and you have to remember that calling functions takes time. Most servers have a 30s limit on the execution time.
So increasing the execution time as your site grows is a normal procedure as the demands on the server grows.
Hi Shane,
I am sorry to have to report that the bug might still be there...
The max exec time is set to 4 times the time before and the images are not loading. Now I wonder if when I said that it worked, I might have looked at a wrong page ( a page with less images) a copy of the original, that I used to test and hunt down the bug...
Have you/the support team found anything else, or are you (very) sure that the bug has to do with the php execution time?