Thanks for your replies.
It was always my intention to write a scheduled task (using Moodle's Task API) however i was reluctant to use Moodle's DB manager ($DB->get_manager()) within this task due to the warnings throughout the documentation that this should only be used in the upgrade.php script. However after going ahead with this anyway and doing some testing, I can't find any issues and it all seems to work. Also, when i uninstall the plugin, the custom table gets deleted correctly.
Mihir J - I was reluctant to use an event because (like you've said), it would be quite a complex script and our installation already has a number of custom observers defined.
Cheers