It occurred to me that delaying the startup of XBMC itself was worth a shot, so off to google I went and found this tip.
Edit your startup applications so the xbmc entry contains the command
bash -c "sleep 10 && xbmc"
This postpones the launch for 10 seconds and fixed the problem for me. Might help someone else as well. :)