This is generally caused by the device having a low amount (or none at all) of memory. When the memory gets lower (lower than 12MB in some cases, although there is not a set number) the device will start deleting messages and/or call logs to conserve memory. You can check your available memory by going to Options > Status and checking the File Free parameter.
The quickest way to free up some memory is to perform a hard reset. Remove the battery from the device (while it is still powered on) for about 30 seconds, then reinsert. Also, look at the links below for ways to maximize the memory:
http://blackberryfaq.com/index.php/How_do_I_free_up_memory_on_my_device%3F
http://blackberryfaq.com/index.php/Why_is_my_BlackBerry_losing_its_call_logs_or_message_logs%3F
