Hello,
"vmcchk" variable is always considered non-SEF by JoomSEF and appended
to existing URL. That is default JoomSEF behaviour.
The only way to remove it is to disable cookie check in VM or adjust the
code of the extension.
As regards the other non-SEF URLs you mention, most likely the reason
will be, that they are no parsed thru Joomla SEO API when generated.
This may be an error on the VM module / template level, not using the
proper API.
You may be also right about the internal redirects, but then the reason is the same - that the redirected URL is not being parsed by the SEO API.
Anyway, the redirection problems can be "fixed" by setting the Redirect non-sef to sef URL in JoomSEF configuration.
I think that getting other product will be of no use, as this is issue on VirtueMart level, not on the JoomSEF level. (this means, that any adjustment of the behaviour need to be done on VM code level; except maybe the vmcchk addition, that is controlled by JoomSEF VirtueMart extension)