I also had this problem on my E51, but have now managed to find the cause. It actually has nothing to do with the SIM card, so don't bother replacing it.
If the phone is kept in one place and isn't moved, the message never appears, but then that defeats the purpose of having a mobile phone!
The problem is caused by the connectors on the battery, which should form a tight grip around the the pin connectors of the phone. The battery that came with my phone never caused the problem, but when I inserted a replacement, every now and then when I put the phone in my pocket, the 'Insert Sim Card' notice would appear
I then compared the two batteries and noticed the replacement's connectors were further apart than the original's. Carrying the phone in my pocket obviously caused some movement, which momentarily disconnected it from the battery and caused the phone to error.
Since then, I have only used the original battery. However, I suspect the problem could be fixed by using a small instrument to bring the battery connectors closer together or by inserting a small piece of aluminium foil to ensure a constant connection.
Not sure, but this may also work for N95/E65 users too.
The E51 is a fantastic phone and the best one I have used to date.