Legally, one state cannot make a vendor in another state collect sales tax on an item shipped to that state (Ie: if I ship an item to NY, NY State cannot make me collect sales tax on the sale because I dont have a physical presence there). That was decided back some time ago in Quill Corp. vs. North Dakota. BUT, some states have gone after online cigarette sellers (I think all they've managed to do is to force them to turn over customer lists so that they can then go the customer and collect the tax, but I'm not 100% sure on that).
edit - see posts below - according to federal law tobacco tax is required to be collected. So, while they cant make you collect sales tax, they can make you collect tobacco tax. Thanks Tone!
On a similar note, Calif is working on a reverse use tax on alcohol, which, if passes, will make california vendors collect california tax on wine and other alcoholic products that are shipped out of state.
If it's simply merchant acct providers not wanting to provide merchant accts to vendors, there are ways around that, just like how some of the online casinos got around the federal law against transactions from banks or similar institutions to online gambling sites; they simply introduced a fourth party to the mix for the money to go through. I dont know if theyre still doing that or not, but I know when the law first went into effect they were doing it.
Age restriction delivery can be handled the same way the wine vendors are doing it (some use a 3rd party to verify age, others simply send UPS or Fedex with Adult Signature Required - but worth noting that if the delivery person fails and lets a minor receive it, the responsibility, blame, and any penalties can fall back on the seller rather than the delivery company)
But, here's a question - does the Waxman bill have any sort of restrictons regarding online sales of tobacco products? If so, and if ecigs get legally defined as tobacco, we might be screwed...
(edit to fix a couple of things)