Weird indeed.
File and Printer Sharing does work over netbeui...no question about that becuase I use it as well.
My only point was that vnc would not work over netbeui...only tcp.
Here is the FAQ from the VNC website:
Can I use VNC over a modem without using TCP/IP?
Not at present. VNC could run over other transports such as RS232, firewire, USB, modems, IrDA etc, in fact, anything which gives a reliable 2-way connection. At present we just use TCP/IP, because it's convenient, ubiquitous, and easy to route. This means that you can use VNC over anything which supports TCP/IP, so using it over a modem is just the same as any other network, once you have Dial-Up Networking set up. If you need to communicate directly between two machines without going via the internet/intranet, then set up a remote access server on one and dial in from the other.
NO netbeui support. Are you running DNS on your server? Is it possible that your machine is resolving the computer name into an IP address?
Also, I see that you said It worked for both the static IP address
That means that you are using TCP on the lan as well. Netbeui does not use IP addresses. So, even though netbeui is installed, it is not the primary protocal for your lan. Your lan will support netbeui, but any app wanting to use tcp/ip will be able to. this is why vnc is working for u on the lan side.
remove all your pcs from the internet and then uninstall tcp/ip..only leave on netbeui and file/print sharing...try using vnc then. you will find that it cannot resolve the computer name and make a connection.
Thus...i'm trying to stay on topic here and help Dug out

... if using vnc on the lan is important (ie u want the vnc connection to be as fast as possible) then tcp on the lan is a requirement. This, btw, is a very secure setup sicne the server hsa two nics and File/Print sharing is only bound to the internal nic (as i stated above).