I've never met anybody who has managed to get ICS (internet connection sharing - a feature of windoze which enables another PC to get internet access through an internet-connected PC) to work.
I've tried it myself with a bluetooth PDA, with no luck, same with a wifi PDA.
ICS is best avoided. If one needs internet access on a PDA, get a broadband (assuming you are on BB) router with wifi (Linksys do nice ones), set it to Infrastructure (non Ad-Hoc) mode, get a wifi card for the PDA if not internal already (one can get a compactflash one for about £50) and it "should just work" (famous last words)......