Try syncing with appbrain before making the swap, then resyncing after. I had shapewriter on my phone and synced my apps with appbrain. Shapewriter had already been taken out of the market, but I had to hard reset. After the hard reset, i re-synced with appbrain and it reinstalled shapewriter even though it was no longer in the market. Not sure how it worked but its worth a shot if you cant find the apk.
