Machines spitting out blocks?

I believe it's actually the pipes spitting the items out, not the machine. Standard buildcraft pipes only test for enough inventory space when the item reaches the end of the pipe, not when it starts moving in that direction.

Try finding the Advanced Buildcraft Objects/Pipes addon, one of them has advanced insertion pipes, which will check if the connected inventory actually has enough space to accept an item. If there is enough room, it will instantly put the item in, and if not it will continue along the next pipe (if there is one). Alternatively, try redpower tubes, they will bounce items that can't enter an inventory back along the tube.

Last solution would be an obsidian pipe close enough to where the items are being dropped, that it can suck them up and send them back into your sorting system.

Correct.