Yikes kebb...! I assumed (note the "ass" in the word assume...

) that you had your LAN machines assigned IPs that are in the "reserved" address space (eg., 192.168.0.1...etc) and had some kind of proxy box setup with NAT that funnelled your LAN's data through it out to the net...
So basically what you're describing is having your machines on a hub (or switch for those fancy dancys out there who don't think that 10MB/s is enuf...LOL) with your internet connection (DSL? Cable? T1 at school/work?) also plugged into it for access out...? What you're describing is sortof rare if this is a home LAN (with multiple IP availabilty due to the cost of additional IPs, but is obviously being done...

)
If this is a home LAN, then you might want to consider getting some kind of free/shareware proxy software for one of your machines or get an old machine to act as a standalone firewall, etc., pop a 2nd NIC in it, and have all of your LAN boxes funnel out through that. Then you can assign fixed IPs to each of your machines behind that NAT box and the NAT box itself will use DHCP (that's what the "obtain an IP" thing does..) to get a valid address from your ISP. This way, you get your LAN configs all setup and working and then leave them that way!
This is what I'm doing here at home where I have 9 machines behind a Linux firewall/NAT server, with 3 of them running UT (one of which is running as a dedicated server).
Since you have dynamic IPs, it sounds like your machine isn't getting the complete DNS, router, etc., info when you obtain the new address (meaning that your ISP's Name server info is not getting set to reference your machine and/or for your machine to know about it), thus you don't know who your other boxes are and they don't know you.
Question - and I've seen this enough with 95, although 98 doesn't do it as much... when you've removed your TCP/IP settings and rebooted (hopefully you rebooted), then put them back (and then it asks you to reboot again), did it take a long time to shutdown or seem like it hung? Sometimes I've had situations with TCP/IP not completely modifying the registry correctly and then it only half works or whatever when it boots (or I forced it to shutdown and boot...).
Also, do you have an "AOL" adapter or equivalent device showing up in your networking properties? I think by default, windud sticks a dialup adapter device in the networking properties window alongside a reference to your NIC (even if you don't have a modem), and then sometimes, your TCP/IP ends up "binding" to that instead of to your NIC...
Also, when you first boot up and are in windoze, go to "Start", "Run", then type in on the command line "winipcfg" (without quotes). If you see nothing in the little box that comes up but "0"s and/or at the top of the box, there's some reference to some dialup adapter or something other than the brand of your NIC, then there's your problem right there - your machine isn't blapping correctly to get its IP and/or some other device is taking precedence (like a dialup adapter or modem). If you see some numbers (like 255.255.255.0) and an IP address, then at least DHCP is working on your machine okay and you're getting an address - and it's now down to a matter of resolving your hostname...
Try some of this and see what happens if you haven't already....