وكثير من المتاعب التي تعرض لها في بداياته, أصبحت عنده ذكريات طريفة. من ذلك أنه عندما كان طفلاً اتفق مع أحد متعهدي الحفلات أن يغني في سرادق أقامه ذاك المتعهد بمناسبة مولد سيد البدوي.
ويبدو أن الشرطة علمت أن طفلاً سيغني في السرادق. وهذا ممنوع قانوناً. وقبل أن يبدأ محمد فوزي الغناء جاءه شرطي يدعوه للذهاب إلى قسم الشرطة بناء على طلب الضابط المناوب فرفض الذهاب وقال للشرطي بأسلوب الواثق من نفسه:
- أرجو أن تقول لحضرة الضابط (إن الجمهور ينتظرني للغناء, ومش عارف ح انتهي من الغناء ايمتى وإذا كان عايزني يتفضل يقابلني هنا).
وانصرف الشرطي, وجاء دور محمد فوزي بالغناء فصعد إلى المسرح, وبينما كان يغني حضرت دورية شرطة وأغلقت السرادق, وأوقفت الغناء فيه, بسبب رفض فوزي الذهاب لمقابلة الضابط ولما علمت الفنانات اللواتي كان لهن فقرات في الحفل بإغلاق السرادق بسبب ذلك المطرب الصغير, تجمعن حوله وانهلن ضرباً عليه بكنادرهن الحادة ذات الكعوب العالية. وبقيت علامة (العلقة الساخنة) على وجه فوزي أياماً طويلة.
ومن الأمور الطريفة عند محمد فوزي أن الوحي الموسيقي لم يكن يأتيه, في مكان شاعري أو في طبيعة جميلة, بل كان يأتيه الإلهام في الحمام وهو يستحم, فمعظم ألحانه الغنائية بدأ يدندن بها وهو تحت الدوش.
وعانى محمد فوزي في بداياته الفنية من البؤس والفاقة, وكان يضطر أيام الإفلاس لأن يكون فطوره وغذاؤه وعشاؤه من الكنافة البسبوسة والليمونادة وكان يسجل ما يأكل على الحساب.
وعندما يكون في حالة مادية جيدة يتناول اللحمة, ومرة كان يغني في أحد ملاهي الاسكندرية وفي آخر الليل عندما ينتهي عمله في الملهى كان يتناول سندويشات لحمة من بائع لحوم على عربة يقف أمام الملهى فيدفع فوزي للبائع شلناً فيصنع له البائع سندويشة فيها لحم فاخر.
واستمر محمد فوزي يتناول اللحم من هذا البائع لفترة طويلة أثناء غنائه في الملهى وفي إحدى الليالي خرج من الملهى فلم يجد البائع ولما سأل عنه أخبروه أن البوليس قبض عليه, لأنه كان يبيع لحمة حمير فصرخ محمد فوزي قائلاً:
- على كده.. أنا أكلت من عنده حمارين!..