Is this possible: Vi ska ha skickat breven.
No, it would mean "should have" (I'm native)
Att utelämna "att" är numera helt okej.
Yes, for most cases where it is optional, it is accepted with or without the att.
My Swedish girlfriend is a muppet