I am running VersionPress on my shared cPanel hosting. The problem is that I was not able to create global wp alias for WP-CLI. I had to modify VersionPress files to include full path to WP-CLI binary. This changes will be lost with next update.

The solution would be to create a new vp config option for the WP-CLI path (simmilar to VP_GIT_BINARY) so you can change the WP-CLI path just by running something like
wp vp config VP_WP_CLI_BINARY '/custom/path/to/wp-cli.phar'