How to detect a rejected transaction? If the nodes I connect to don't support the BIP 61 reject message, how do I know that my transaction was eventually rejected by the network (e.g. due to my bugs)? Is there any timeout or whatever after which it's reasonable to assume that my peers will never relay the transaction?
There are no timeouts, and a valid transaction can be mined at any time.

The only thing that can ensure a particular transaction won't get mined in the current block chain is to make it invalid.  The only practical way to do that is to create a confirmed double spend---another transaction that spends one of the same inputs as the transaction you don't want mined.  Once that double spend is confirmed, your original transaction can't be added to a block in the same block chain as the confirmed double spend.