b) I can run 115,200 baud on my no-crystal setup with no hiccups to speak of.
The datasheet claims the internal oscillator has an accuracy of 10% at 3V and 25C. So, it comes down to this question: Is a 10% clock difference enough to stop serial communications from working? Assuming I did the math correctly, the answer is yes, it will stop serial communcations from working. The result will be framing errors.
I have a 168 that's about 2.1% off and a 328 that's about 4.9% off (4.5V, 20C). My 168 should work fine but my 328 probably won't work.
a) the lilypad works fine and;
There is a register that allows the internal osciallator to be calibrated. According to the datasheet, this gives an accuracy of 1%. But I have no idea if the Lilypad's oscillator is calibrated. I'm just saying that may be how they did away with the crystal.