@ziawj2,
Firstly, do you not have the ability to talk with your friend in any way? Many people would consider a letter a cowards way out, and the very act of writing instead of talking to them (if talking to them is possible) may upset some people.
Secondly, of the 3 choices for opening 3) is the best. You opened with a relationship statement (thank you - ie. I appreciate the following you did for me).
Leave BUT out of your sentence, because in English, everything that comes before BUT tends to be disregarded :
"I don't mean to be disrespectful but... (I'm about to say something disrespectful)"
As for the rest, how about "Unfortunately I've had a big move recently, and after unpacking, I can't find it. I'm so extremely sorry - I have backtracked and tried everything to locate your book, because I know how much it means to you. "
The ending depends on exactly what is involved in this book. If it has notes of great sentimentality in it, then the ending would change. For example, a personally autographed book from your friends all time favourite author could never be replaced by buying a new book.