You might find a way to decrease those deadlocks using some MySQL configuration, maybe increasing locks or some other configure.
We just retry those statements, and that will not be causing you any problem.
When you don't using persistent messages, obviously MySQL is not used.
Could you try upgrading to 1.4.0.SP3?
Also, on mysql, if you go to a mysql console and type "show innodb status"
It will tell you what's causing the deadlocks.
Based on that you may be able to add some indexes to prevent the deadlock.