@NdunguThat method looks tedious since (millions of) guys would have to update their SIM cards over the air all the time given the dynamic nature of the number of companies receiving payments using Pay Bill that enter and leave their master list. I guess they could have the SIM app running some USSD code in the background to fetch the menu/submenu info from their servers whenever you select the Pay Bill option i.e. in such a way that the USSD reply message is parsed by the SIM app and presented to the user in the usual MPESA format instead of having to reply 1 for this, 2 for that etc.
That should be possible since I would imagine the SIM app already parses the received status codes whenever you confirm a transaction with MPESA, as in whenever it says 'sent' the SIM app has basically received a USSD reply confirming the order receipt, right? I may be wrong though, 'tis just my own evaluation since i'm not a mobile guru...