Deadlock between two databases
If you are only accessing your database, it is highly unlikely that deadlocks you are experiencing are caused by other customers that happen to have their database on the same server - they'd have to be intentionally crossing database boundaries with transactions, and they'd most certainly not have the ability to do that. However we need a lot more information about what kind of deadlocks you are seeing, as they could involve system objects, etc. Are the objects involved only in your database? Have you looked at the deadlock graphs at all, or are you just responding to "deadlock victim" messages? Lots of info in this StackOverflow question about interpreting deadlocks, but you need to capture the graph using Profiler or some kind of monitoring tool (for which you may need to ask the host's assistance).