In their answer to my question about Odin and Loki being blood brothers, chaimedes quotes a footnote in Henry Adams Bellows' translation of the Poetic Edda that claims Odin and Loki were "often allied in enterprises":
9. There exists no account of any incident in which Othin and Loki thus swore blood-brotherhood, but they were so often allied in enterprises that the idea is wholly reasonable. The common process of "mingling blood" was carried out quite literally, and the promise of -which Loki speaks is characteristic of those which, in the sagas, often accompanied the ceremony; cf. Brot af Sigurtharkvithu, 18 and note.
I did find a mention to such an enterprise in the Lokasenna:
50. "Though on rocks the gods bind me | with bowels torn
Forth from my frost-cold son,
I was first and last | at the deadly fight
There where Thjazi we caught."Source: Poetic Edda/Lokasenna, Wikisource
More details on Thjazi's story can be found in the Skáldskaparmál, which starts with Odin, Loki and Hœnir setting on a journey together.
One adventure, however, is certainly not enough to support Bellows' claim. What other adventures did Odin and Loki share, as allies?