The BEMCLI switch expects the use of wildcard characters.
Workaround:
Use wildcard characters in the BEMCLI command to search files/folders within the catalogs.
Get-BEAgentServer "Win2k16" | Search-BECatalog "Test\DIR-1025*" -PathisDirectory

Note: Backup Exec UI (not BEMCLI) limits the search to show 10000 entries only, hence BEMCLI may be used. ( As noted in the problem section)
There are currently no plans to address this issue by way of a patch or hotfix in the current or previous versions of the software at the present time. While this issue may be resolved in a future major revision of the software at a later time, it is not currently scheduled for any release. If you feel this issue has a direct business impact for you and your continued use of the product, please contact your Veritas Sales representative or the Veritas Sales group to discuss these concerns.