The coins aren't lost, but they can be "stuck". Your client declares the coins spent, but the network doesn't ever include it in the blockchain. By default, you can't send the coins elsewhere, because the client doesn't believe you own them anymore. However, if you clear your client's memory pool, or can import your wallet into another program, you can try re-sending with a higher fee. Once that new transaction makes it into the blockchain, then your client will see that and invalidate the old transaction.
Also, I have no intention to bash bitcoinj, but I'm curious why the fees aren't implemented yet..? The way I did it in Armory is very simple and seems to work very reliably. It's also very close to what the network expects (ignoring block-fill considerations).
Here's the relevant code in Armory.
In order for a transaction to be free, three conditions must be met:
--Transaction is less than 3.5 kB (approx)
--Transaction does not have any dust outputs (<0.01 BTC)
--Transaction inputs have priority-sum greater than 1 bitcoin-day-per-250-bytes
If the transaction cannot be free, then use the folllowing fee:
--If transaction is less than 3.5 kB, use fee 0.0005 BTC
--Otherwise, use (0.0005 * roundup(numkB))
There are more fees required to get it into
the next block, if there's already a lot of transactions being included in the next block. But this fee will always get it included in
one of the next blocks. So far, I haven't experienced any users (or myself) getting coins stuck in Armory.
