I actually did send bitcoins (with no fee) to another wallet on a smartphone, but while the trasaction cleared the bitcoins from my pc wallet, it did not appear on my smartphone even after several minutes. I then recovered a backup and sent the same bitcoins to another address (MtGox) this time with a fee and they did move to MtGox. I suppose I double-spent them, but it worked.
This very likely means the network never heard about the first transaction.
If it did, the network would have coughed up the old transaction and cancelled the new. The network definitely would not have accepted the double spend.
If the network did not hear of the first transaction, then that is a problem. The transaction did clear my wallet. I suspect there may be issues with non-fee vs fee transactions with the state of the network, but the smartphone client may have been a factor. This was a one time occurrence.