Update: Our web-hosting provider has moved our website to a different server, and this now seems to have ‘cured’ the problem. However, they did note “the plugin is requiring more than our shared hosting limits of 60 secs execution time”, so we can only assume the Wordfence plugin does have some limitations when used on certain server configurations.
