Q: Where does My Genius & Library go!?

It sounds like something (or somebody) was moving items on your computer that shouldn't be moved.

Image of iTunes folder structure Dec. 2011 - https://discussions.apple.com/thread/3547807

see also:

Image of folder structure and explanation of different iTunes versions (turingtest2 post) - https://discussions.apple.com/message/13025536

Did you read http://support.apple.com/kb/HT1660   about Previous Libraries?

Did you see a message" The file iTunes Library.itl does not appear to be a valid music library file.  itunes has attempted to recover your music library and renamed this file iTunes Music Library Damaged."?

iTunes: How to re-create your iTunes library and playlists - http://support.apple.com/kb/ht1451

Yes, you could re-build your library from scratch.  It will just be music files and no playlists, ratings, last played, etc.  If you use one of the method outlined in the article to import the .xml you might be able to recover most of that too.