Is it that they look like txids but don't appear on the network, or are they totally bogus?

If it's the former, my guess would be that the Poloniex wallet has somehow lost track of one or more of its unspent outputs, and is trying to double spend. The tx is generated successfully, at least from the point-of-view of the Poloniex wallet, but since it has invalid inputs the network quietly ignores it.

Any ideas how Poloniex "fixes" the problem when you report it?