Magmi stalls on the first line, only sometimes errors

[nothinglesss]

Hello! I want to apologize in advance - I'm not a coder and I'm really just looking for some help in figuring out why Magmi isn't working for me. I couldn't find a paid support channel so apologies in advance if this is the wrong place to post!

Background: I have a large Magento catalog with just over 400,000 SKUs. Most of those are child products (sizes) of the parent products (clothing). I only use Magento for the M2E plugin, for syncing my products to eBay and Amazon, it's not an open store. Version 1.9.4.0, and it's hosted with a webhost who specializes in Magento hosting and the servers are supposed to be optimized for Magento (simpleservers.co.uk).

I have been using Magmi for importing and updating for years without any problems, until last week. It just stalls - usually at the first row, sometimes after a few rows. Sometimes it shows up an error like this one:
SKU 151150402-M - 5 SQLSTATE[40001]: Serialization failure: 1213 Deadlock found when trying to get lock; try restarting transaction -

But other times there are no errors, it just hangs and nothing happens. It could be sitting for 2 hours with nothing happening. And this is with a CSV file of 10 lines, or of 100 lines, it doesn't matter. Normally Magmi processes these for me in seconds.

What I have tried:
I first of all contacted my webhost as I thought it was a server problem. They say it's not, there's nothing in any error logs and there's plenty of resources on the server.

I have tried using Magmi CLI via the command line, but same thing there, it just hangs.

I have tried re-doing and changing my CSV files, even making a new Magmi profile that only has 9 columns in it. No difference.

I have tried reinstalling Magmi 0.7.23 from scratch, and installed 0.7.22 in a separate folder too in case the newer version broke something - no difference.

Here are the settings I'm using for Magmi:

And here is the outcome when it DOES show errors (again, sometimes it just hangs with no errors):

And here is the simple CSV file I'm using at the moment:
leggings-test.txt

I'm really lost on how to further troubleshoot this! What can I try, where can I look, to find out why it's suddenly stopped working? Thanks so much in advance for any advice, I'm really at my wit's end!!

[crysix]

This is definitly a server/database problem, so your webhoster is lying.

Deadlock happen when two transactions wait on each other to acquire a lock. Example:
Query 1: lock A, then B
Query 2: lock B, then A

Another reason for deadlock in database can be missing indexes.

I would recommand to dump the hole database, drop it, and create a new database and import your dump again. This could help sometimes.

[nothinglesss]

Unfortunately the server times out when I try to dump the entire database - it is a whopping 7.4 GB in size! Thanks for the advice though, I'll take this back to my webhost. If you have any other ideas or tips, do let me know! Thanks!

[crysix]

mysqldump shell command should be able to handle that size easily but not phpMyAdmin and other "visual" tools.