mobi2mobi is for editing the metadata. Normally that is not necessary since calibre can do all the work for you, but in case you need to check something you can use
Java Mobi Metadata Editor.
Are these books Personal Documents, or "ebooks"? (The difference is in the exth header 501, cdetype -- a value of "EBOK" displays as G-d/Amazon intended, a value of "PDOC" displays that ugly "Personal" banner.)
A PDOC will always have the cover extracted from the ebook file, and an EBOK will always depend on downloading the cover from Amazon's servers, which can be problematic so calibre sideloads the cover for you.
And a book with an ASIN will automatically be treated as EBOK I believe.
I would think the problem has to be the indexing (no other explanation I am aware of for books not showing up) so I would give the search-for-nonsense-string another try. There is an option somewhere, though I have an older firmware and am not sure what yours looks like. (Mine is just setting the search between My Items, Dictionary, This Book, Wikipedia etc. but the UI was changed...)
Regarding AZW3, that is another name for KF8 (Kindle Format 8) / mobi8 (mobipocket database format 8) / AZW3 (ebook-file.azw3)
The advantage of KF8 over mobi7 is better support for General Stuff (like having embedded fonts), internally cleaner and able to be cleanly unpacked into the original source, support for updating additional metadata e.g. cover, also, it handles highlighting hyphenated words better... no reason whatsoever to use MOBI unless you have a device that doesn't support KF8.
To see what firmware you have, go to Menu ==> Settings == Menu (again) ==> Device Info
Your Kindle Touch 2/KT2 (as we call it) first shipped with the 5.6.x line of firmware. It is for sure recent enough to support AZW3.
