I've been trying (in vain) to create a RCP Application that runs some code when starting. This host RCP Application is not Eclipse, so I guess that's the reason my plugin extending org.eclipse.ui.startup doesn't seem to work. I've even tried putting its dependencies on the same plugins/ folder but it was of no avail.
What path should I follow to accomplish the described task?
By design, this is not possible.
Start-up time is very important in GUI applications. Many many plugin authors believe that they need to do some kind of initialisation during start-up... if Eclipse actually allowed them to then the application would take hours to start. Instead plugin authors should lazily initialise upon first interaction from the user.
If there is something special about your plugin in relation to this application then you need to talk to the application author and ask them to provide a hook for you to plug in your initialisation code.