Hola, no se si pasará lo mismo con las dll que con los exe, pero por lo que cuentas parece ser que sí.
Lo que pasa es que seguramente se necesitan componentes que se instalan con VB.
Haz la prueba de, en lugar de copiar el archivo generado por visal, anda a Empaquetado y Distribución (creo que así se llama) y agrega tu proyecto. Esto generará un archivo de instalación de unos 20 megas que agregará todos los componentes (dlls, ocx) que tu programa necesite. Esto lo instalas en los pc sin VB y debería funcionar.
Saludos
<p align="center">
<EMBED src="http://www.webmagic.cl/firmafdw.swf" quality=high wmode=transparent WIDTH="260" HEIGHT="60" NAME="wc"></EMBED>
</p>