Mail.app rules cannot run on mail they do not have. That is to say- a rule cannot be applied to a message that doesn't exist. Mail.app must download the email in order to parse it in order to run the rule against it.
Now, that said. If you're dealing with a POP server situation where Mail.app is configured to not delete anything from the server - it should still delete messages you explicitly delete.
Get into your Mail.app prefs, accounts. Select the account in question, and go to the Mailbox Behaviours tab. Check the 'Move deleted messages to the Trash mailbox' checkbox. Now when you delete something, it'll go to the trash. Yipee. I prefer never to have Mail.app delete something itself so mine is set to "never", but you could set it to automatically empty the trash at whatever interval you like.
Now - if you set up your rule, whatever emails are downloaded onto your computer and match the rule will be deleted right away. Or at least moved to the trash and deleted at your next interval.
I think when you talk about your PC experience you're talking about Outlook + Exchange, which has a unique feature where you can have the rules actually live on the exchange server and are executed there, rather than on your local computer. Is this supported by Mail.app on a Mac? No, not that I know of.