can you call the stored procedure from your database shell? (I have no idea what mssql stored procedures should look like, but it's the first thing to try, because if it won't work from your database directly, it's not going to work from a Perl script).
what is the error message that was in the database's error string, that friedo suggested you take a look at? (There might be someone on here who can read minds, but it's sure not me)
could you ennumerate those 'every ways' that you've tried, and what the error messages were from them?
could you give more information about the script, such as which DBD you're using?