Losing your wallet or your keys or your cell-phone is
無くした、なくした (I lost it, I left it somewhere)
無くなった、なくなった (It's lost/gone)
無くしてしまった、なくしてしまった (I lost it, I left it somewhere)
無くなちゃった、なくなちゃった (It's lost/gone)
etc.
While you could use うしなう, it somehow feels too formal and too final, and its not entirely appropriate for handheld items. It might be better to use in situations where a big thing is lost to fire or economic collaps (like a house or a business). Or, as you said, losing some intangeable item like words or memory.
Be aware that 無くなる (to lose) is different from 亡くなる (which means to die), but can be similar in context and usage.
うしなう can also be used to indicate a death. Sorry, it gets confusing, and its one of those situations for which the casual learner doesn't get a lot of practice.