No you shouldn't use NetBEUI at all on either machines!!!!!!
 
You have to have TCP/IP installed for web, mail etc, so use that for NetBIOS traffic.
 
NetBEUI doesn't utilise error checking and can lead to data corruption on problematic networks.
 
In short, don't install NetBEUI.

Using a router? You will need TCP/IP (unless it supports IPX--ick!) for access across it. If you have TCP/IP, then you wont need NetBEUI. By default, TCP/IP should install with "enable NetBIOS over TCP/IP" selected. This will allow you to use the simple names for your PCs(or "DOMA34XDY-E45" and such if you chose the default ones) when connecting to them.
 
Is the router a gateway as well? If so, it may support DHCP and you can use the router to issue all the info you need to get the PCs talking to each other.
 
------------------
Regards,
 
clutch

Thanks Guys,
 
I enabled Netbeui because I was clutching at straws trying to solve another problem.
 
I've removed Netbeui now.
 
All working fine.