I think this will work, not sure but here is a tip for all of you.
This hint will allow your Xbox to obtain its IP, DNS info, and so on from the Mac using DHCP. You need to have administrator privileges on the Mac in question, and the procedure is different on 10.4 vs. 10.5. (Presumably older systems were similar to 10.4, but I haven't tested on anything older than 10.4.10.).
10.4:
I haven't had much time to interact with the 10.4 machine I have access to, so I haven't tested this as much. Some variation on this procedure may be necessary to get the change to stick -- in particular, you may need to perform it more than once, or start and/or stop Internet Sharing before performing it. Also, the restart at the end may be unnecessary (though you do need to start and stop Internet Sharing somehow). Please post your experience in the comments, if someone hasn't already.
Start Internet Sharing if it's not already running.
Open NetInfo Manager, located in /Applications » Utilities. Authenticate as an administrator using the lock icon in the lower-left.
Navigate to the /config/dhcp node (so that dhcp is selected in the browser pane).
In the lower pane, find the reply_threshold_seconds property and change its value from 4 to 0.
Quit NetInfo Manager and then restart your Mac.
After the restart, open NetInfo Manager again and confirm that reply_threshold_seconds is still 0.
10.5:
The following procedure is confirmed to work as written.
Start Internet Sharing if it's not already running.
In Terminal, type cp /etc/bootpd.plist /tmp/bootpd.plist
Stop Internet Sharing.
Open /tmp/bootpd.plist for editing using TextEdit or whatever.
Locate this section of the file, near the end:
<key>reply_threshold_seconds</key>
<integer>4</integer>
Change the value 4 to 0.
In Terminal, type sudo cp /tmp/bootpd.plist /etc
Start Internet Sharing.
If you want to, check that your change to /etc/bootpd.plist hasn't been reverted.