I finally grew tired of the multiple unnecessary 404 errors being generated on the page views of the site collection. I'd spent a fair bit of time looking for how to remove the orphaned items before I opened MS case.
Eventually we discovered the solution and again it was quite easy once we knew what to do.
For some background, here's the Elements.xml of the Sandboxed Solution:
To remove these orphaned files I used powershell:
$s = get-spsite https://foo.com
$uca = s.UserCustomActions | select -first 1
$uca # Visually validate this one to delete before running the next command