Craig,
This is the chip you want. NE2000 like the RTL8019AS, but 10/100; 5v tolerant, but runs on 3.3v; LQFP-128 instead of TQFP-100. I've got one wired to an Mega128 in 16-bit mode, due to a similar migration from the RTL8019AS (for identical reasons). Only very slight extensions from your NE2000 driver to configure the 100Mb features.
formatting link
For prototyping, this built board is actually cheaper than buying the chips from Singapore (at least for the USA), and he'll sell you 1-off chips too. Even with your proximity, you may find he offers a better deal. (ASIX wanted $60USD for qty 1, plus s&h from Singapore.)
formatting link
The fellow who hosts this page also wrote an article in ~October 2002 in CircuitCellar magazine discussing how to connect the Mega128 (in an Atmel STK500 kit) with this proto board.
You are spot-on in your reasoning for switching controllers, although technically the failing is in the RTL8019AS' ability to auto-negotiate. It's just not part of the 10Mb spec.
While the 8019 can be forced into full-duplex mode to eliminate collisions, detecting whether the switch is in FDX mode is a problem. And this is also one of only two 8019 settings you can't elect through a register - you have to install or emulate the EEPROM.
Cheers, Richard