Clear recents list in Screen Sharing on OS X El Capitan
Finally stumbled across the answer to clear the docked recents list, ridiculously easy of course:


In the Screen Sharing app, pick menu Connection, Open Recent, Clear menu (as described in the question)
Quit the application
Undock its icon (right click on it within the dock, pick Options, pick item Keep in Dock).  
Reopen the app (Finder, menu Go, item Connect to Server, type "vnc://host:5901" in the Server Address field, click Connect).
After it opens, redock the icon (same as #3 above). 


After this, the recents shown in the right-click context menu should be gone.

p.s. thanks @grgarside for the clean-up edits