I think I'm missing something here. Isn't it easier to use a coin control patch/utility to pick e.g. 10 of these tiny outputs, combine with a large output of mine (so the resulting priority is high enough) and create a single output to myself? By repeating this procedure we could also reduce the UTXO set without having to fiddle with raw transactions and/or edit any hexdump.
Thats fine too, though it does result in moving more data than strictly required (the extra signature for the coins you're moving just as a source of priority) and priority also limits how much you can do thus for free.
What you don't want to do is just move one single worthless output by itself... that just further decreases the odds that it'll ever get cleaned up.
Eligius now has a pushtx interface which will directly accept OP_RETURN and other weird txn that eligius accepts:
http://eligius.st/~wizkid057/newstats/pushtxn.php
