I've just recently had this discussion within our team. Our conclusions were to inline the CSS (against having them as separate downloads and relying on expires headers to cache on the phone). some of our key considerations were:
There is a lot of latency establishing a connection, so inlining the CSS has a big advantage on feature phones that do not support caching the files locally with expires header.
For phones that support expires generally also support payload compression, so using compression compensates for the additional css in each download.
This strategy loses out on phones that support expires, but do not support compression. We figure this is a pretty small % of our users.
Addressing @Bob's maintenance point, we keep all the css in separate files on the server, and it is injected into the HTML as this is being generated (serverside is JSF). If you don't have this option, then I agree with Bob - it will become a maintenance nightmare.
Note: We cater to both smartphone users with WIFI (20%), smartphone over 3G/Edge (40%) and feature phone users over 3G/Edge (40%).