Found out that I was probably using the wrong class.
Instead of Microsoft.Web.Services.Security.SignedXml of should use System.Security.Cryptography.Xml.SignedXml. The latter doesn't use the SignatureAlgorithm of the used key to determine what Algorithm to use. Now I can set the Algorithm myself with 'SignedXml.SignedInfo.SignatureMethod' and use a SHA1 key.