Hmm, what I need to be able to do with spending an output twice though is the following:
Create a transaction (no tx fee), send it.
Wait 30 seconds.
Create a different transaction spending the same output (with tx fee), send it.
Would that work? The 2nd tx should get confirmed first since it has a tx fee even though it was sent after.
Probably not.
1) The client won't intentionally double spend so you will need to delete the the first tx from the wallet "history". The client provides no mechanism to do this natively although tools like pywallet can be used.
2) All nodes will drop double spends in favor of the first tx they saw. So in your example you sent tx#1 to all your peers. When you send tx#2 to the same peers they will immediately recognize it as a double spend and simply "drop" (delete) it. Changing to new peers is unlikely to work as your peers relayed tx#1 to their peers who relayed it to their peers, etc, etc, etc, and within a few seconds every node on the planet is aware of tx#1 and will see any attempt to double spend it as invalid and just drop tx#2 without relaying.
The network is intentionally designed to make double spending difficult.
The client is intentionally designed to make creating tx that have a very high probability of being "stuck" (never relayed to included in a block by most clients) difficult.
You can hack around these design constraints but don't expect it to be easy.
This is why Danny indicated you need to wait a few days. If a particular node NEVER dropped tx#1 then it would never store or relay tx#2 however to avoid a memory exhaustion attack eventually nodes will drop the oldest tx from the memory pool. You can't control when your tx#1 will be dropped by other nodes. It will occur as needed with each node acting independently. Until tx#1 is dropped from a particular node any attempt to broadcast tx#2 will mean it is simply dropped by that node. Until tx#1 is dropped by a majority of nodes the probability that it will be able to propogate the network and find one or more miners is very low.
In theory you could bypass all that by sending the tx directly to a miners however most miners don't make their processing nodes known or accept inbound connections. Those that do don't allow replacement of txs in memory pool for obvious reasons (malicious double spend).