How do I know when an order has been paid?

Our orderstaff gets the confirmation e-mail from the system when an order is placed but they don't get any mail when the order has been paid. Is this possible or do they really have to go into the admin to syrvey all orders and check if they have been paid?

This depends on the method of payment.
For credit cards, most PSP's give back a result after capture. This result can be used to auto-update the payment status.
For paypal and likewise methods, there is also a result that is used to update the payment status.
If the status is used to auto-update the order or not, depends on the programming of the payment method plugin.

But if you use a manual processing method, like Purchase Order or Pay on Delivery, you will have to mark the payment status as Paid yourself.

I have my own payment implementation and that code marks the order as paid but I don't want to create an e-mail in my payment code as I want that to be handled by the system itself.

What you are saying is that I have to implement this on my own.