Try using double tildes:
=VLOOKUP(SUBSTITUTE(C1,"~","~~"),A:B,2,false)
The tilde is the special character in Excel to escape other special characters. Use a tilde to make the tilde you want to match a literal tilde (e.g. * in excel find matches any number of characters, but ~* will match a literal *).
The data I used it on is:
A B C D
~Hello 1 ~Hello =VLOOKUP(SUBSTITUTE(C1,"~","~~"),A:B,2,false)
Hello 2
Cell D1 is returning me 1 (meaning it is matching ~Hello).