The rescan switch is supposed to force the client to look through the block chain for transactions that it missed the first time, to double check that it has everything. But if it isn't appearing in that list, then the rescan won't help out.

One thing you could do to eliminate all possibilities is to go to blockexplorer.com and do a search for either the address you sent from, or sent to, and see if the transaction is anywhere in the block chain. If it's there, then the rescan switch should find it. If not, then the transaction hasn't been broadcast to the network, and I'm not sure what to do next.