How come my my HTC Desire Z sometimes doesn't notify me about a new SMS?
How much free internal space do you have on your phone?  When my phone has too many services running or doesn't have enough free internal space then services will get killed left and right, therefore the messaging service won't run to alert me of a new message.  Try uninstalling some apps or moving them to the SD card.  You can check for any unnecessary running services under Settings -- > Applications --> Running Services.