New messages do not show up immediately - HTC Desire Z
Other folks here have suggested that the issue may be with your SIM card:


Recipients complain they receive Text Message from me with a half hour delay


I was having a similar problem which was resolved when I reset my phone to factory settings (for other reasons). It might be worth asking your carrier for a new SIM, though. 

PS. This user asked about sms receipt delays -- a different but related question.