Hey, now it works!
This is what I did:
- Set baudrate to 9600 and tested with my flytron GPS which worked fine (as expected).
- Switched back to 4800 baud and connected the EM-411 GPS and now it works!
I know it doesn't make any sense but somehow that seems to have fixed it.